:: Euler circuits and paths
:: by Yatsuka Nakamura and Piotr Rudnicki
::
:: Received July 29, 1997
:: Copyright (c) 1997-2012 Association of Mizar Users


begin

definition
let D be set ;
let T be non empty FinSequenceSet of D;
let S be non empty Subset of T;
:: original: Element
redefine mode Element of S -> FinSequence of D;
coherence
for b1 being Element of S holds b1 is FinSequence of D
proof end;
end;

registration
let i, j be even Integer;
cluster i - j -> even ;
coherence
i - j is even
proof end;
end;

theorem :: GRAPH_3:1
for i, j being Integer holds
( ( i is even iff j is even ) iff i - j is even ) ;

Lm1: for p being FinSequence
for m, n being Element of NAT st 1 <= m & m <= n + 1 & n <= len p holds
( (len ((m,n) -cut p)) + m = n + 1 & ( for i being Element of NAT st i < len ((m,n) -cut p) holds
((m,n) -cut p) . (i + 1) = p . (m + i) ) )

proof end;

theorem Th2: :: GRAPH_3:2
for p being FinSequence
for m, n, a being Element of NAT st a in dom ((m,n) -cut p) holds
ex k being Element of NAT st
( k in dom p & p . k = ((m,n) -cut p) . a & k + 1 = m + a & m <= k & k <= n )
proof end;

definition
let G be Graph;
mode Vertex of G is Element of the carrier of G;
end;

theorem Th3: :: GRAPH_3:3
for G being Graph
for c being Chain of G
for vs being FinSequence of the carrier of G st vs is_vertex_seq_of c holds
not vs is empty
proof end;

Lm2: for G being Graph
for p being Path of G
for n, m being Element of NAT st 1 <= n & n <= len p & 1 <= m & m <= len p & n <> m holds
p . n <> p . m

proof end;

theorem Th4: :: GRAPH_3:4
for G being Graph
for e being set st e in the carrier' of G holds
<*e*> is Path of G
proof end;

theorem Th5: :: GRAPH_3:5
for G being Graph
for p being Path of G
for m, n being Element of NAT holds (m,n) -cut p is Path of G
proof end;

theorem Th6: :: GRAPH_3:6
for G being Graph
for p1, p2 being Path of G
for vs1, vs2 being FinSequence of the carrier of G st rng p1 misses rng p2 & vs1 is_vertex_seq_of p1 & vs2 is_vertex_seq_of p2 & vs1 . (len vs1) = vs2 . 1 holds
p1 ^ p2 is Path of G
proof end;

theorem Th7: :: GRAPH_3:7
for G being Graph
for c being Chain of G st c = {} holds
c is cyclic
proof end;

registration
let G be Graph;
cluster Relation-like NAT -defined the carrier' of G -valued Function-like one-to-one finite FinSequence-like FinSubsequence-like cyclic for Chain of G;
existence
ex b1 being Path of G st b1 is cyclic
proof end;
end;

theorem Th8: :: GRAPH_3:8
for G being Graph
for m being Element of NAT
for p being cyclic Path of G holds (((m + 1),(len p)) -cut p) ^ ((1,m) -cut p) is cyclic Path of G
proof end;

theorem Th9: :: GRAPH_3:9
for G being Graph
for p being Path of G
for m being Element of NAT st m + 1 in dom p holds
( len ((((m + 1),(len p)) -cut p) ^ ((1,m) -cut p)) = len p & rng ((((m + 1),(len p)) -cut p) ^ ((1,m) -cut p)) = rng p & ((((m + 1),(len p)) -cut p) ^ ((1,m) -cut p)) . 1 = p . (m + 1) )
proof end;

theorem Th10: :: GRAPH_3:10
for G being Graph
for n being Element of NAT
for p being cyclic Path of G st n in dom p holds
ex p9 being cyclic Path of G st
( p9 . 1 = p . n & len p9 = len p & rng p9 = rng p )
proof end;

theorem Th11: :: GRAPH_3:11
for G being Graph
for e being set
for s, t being Vertex of G st s = the Source of G . e & t = the Target of G . e holds
<*t,s*> is_vertex_seq_of <*e*>
proof end;

theorem Th12: :: GRAPH_3:12
for G being Graph
for c being Chain of G
for vs being FinSequence of the carrier of G
for e being set st e in the carrier' of G & vs is_vertex_seq_of c & vs . (len vs) = the Source of G . e holds
( c ^ <*e*> is Chain of G & ex vs9 being FinSequence of the carrier of G st
( vs9 = vs ^' <*( the Source of G . e),( the Target of G . e)*> & vs9 is_vertex_seq_of c ^ <*e*> & vs9 . 1 = vs . 1 & vs9 . (len vs9) = the Target of G . e ) )
proof end;

theorem Th13: :: GRAPH_3:13
for G being Graph
for c being Chain of G
for vs being FinSequence of the carrier of G
for e being set st e in the carrier' of G & vs is_vertex_seq_of c & vs . (len vs) = the Target of G . e holds
( c ^ <*e*> is Chain of G & ex vs9 being FinSequence of the carrier of G st
( vs9 = vs ^' <*( the Target of G . e),( the Source of G . e)*> & vs9 is_vertex_seq_of c ^ <*e*> & vs9 . 1 = vs . 1 & vs9 . (len vs9) = the Source of G . e ) )
proof end;

Lm3: for G being Graph
for c being Chain of G
for vs being FinSequence of the carrier of G st vs is_vertex_seq_of c holds
for n being Nat st 1 <= n & n <= len c holds
( 1 <= n & n <= len vs & 1 <= n + 1 & n + 1 <= len vs & ( ( vs . n = the Target of G . (c . n) & vs . (n + 1) = the Source of G . (c . n) ) or ( vs . n = the Source of G . (c . n) & vs . (n + 1) = the Target of G . (c . n) ) ) )

proof end;

theorem :: GRAPH_3:14
for G being Graph
for c being Chain of G
for vs being FinSequence of the carrier of G st vs is_vertex_seq_of c holds
for n being Element of NAT holds
( not n in dom c or ( vs . n = the Target of G . (c . n) & vs . (n + 1) = the Source of G . (c . n) ) or ( vs . n = the Source of G . (c . n) & vs . (n + 1) = the Target of G . (c . n) ) )
proof end;

theorem Th15: :: GRAPH_3:15
for G being Graph
for c being Chain of G
for vs being FinSequence of the carrier of G
for e being set st vs is_vertex_seq_of c & e in rng c holds
( the Target of G . e in rng vs & the Source of G . e in rng vs )
proof end;

definition
let G be Graph;
let X be set ;
:: original: -VSet
redefine func G -VSet X -> Subset of the carrier of G;
coherence
G -VSet X is Subset of the carrier of G
proof end;
end;

theorem Th16: :: GRAPH_3:16
for G being Graph holds G -VSet {} = {}
proof end;

theorem Th17: :: GRAPH_3:17
for G being Graph
for e, X being set st e in the carrier' of G & e in X holds
not G -VSet X is empty
proof end;

theorem Th18: :: GRAPH_3:18
for G being Graph holds
( G is connected iff for v1, v2 being Vertex of G st v1 <> v2 holds
ex c being Chain of G ex vs being FinSequence of the carrier of G st
( not c is empty & vs is_vertex_seq_of c & vs . 1 = v1 & vs . (len vs) = v2 ) )
proof end;

theorem Th19: :: GRAPH_3:19
for G being connected Graph
for X being set
for v being Vertex of G st X meets the carrier' of G & not v in G -VSet X holds
ex v9 being Vertex of G ex e being Element of the carrier' of G st
( v9 in G -VSet X & not e in X & ( v9 = the Target of G . e or v9 = the Source of G . e ) )
proof end;

begin

definition
let G be Graph;
let v be Vertex of G;
let X be set ;
func Edges_In (v,X) -> Subset of the carrier' of G means :Def1: :: GRAPH_3:def 1
for e being set holds
( e in it iff ( e in the carrier' of G & e in X & the Target of G . e = v ) );
existence
ex b1 being Subset of the carrier' of G st
for e being set holds
( e in b1 iff ( e in the carrier' of G & e in X & the Target of G . e = v ) )
proof end;
uniqueness
for b1, b2 being Subset of the carrier' of G st ( for e being set holds
( e in b1 iff ( e in the carrier' of G & e in X & the Target of G . e = v ) ) ) & ( for e being set holds
( e in b2 iff ( e in the carrier' of G & e in X & the Target of G . e = v ) ) ) holds
b1 = b2
proof end;
func Edges_Out (v,X) -> Subset of the carrier' of G means :Def2: :: GRAPH_3:def 2
for e being set holds
( e in it iff ( e in the carrier' of G & e in X & the Source of G . e = v ) );
existence
ex b1 being Subset of the carrier' of G st
for e being set holds
( e in b1 iff ( e in the carrier' of G & e in X & the Source of G . e = v ) )
proof end;
uniqueness
for b1, b2 being Subset of the carrier' of G st ( for e being set holds
( e in b1 iff ( e in the carrier' of G & e in X & the Source of G . e = v ) ) ) & ( for e being set holds
( e in b2 iff ( e in the carrier' of G & e in X & the Source of G . e = v ) ) ) holds
b1 = b2
proof end;
end;

:: deftheorem Def1 defines Edges_In GRAPH_3:def 1 :
for G being Graph
for v being Vertex of G
for X being set
for b4 being Subset of the carrier' of G holds
( b4 = Edges_In (v,X) iff for e being set holds
( e in b4 iff ( e in the carrier' of G & e in X & the Target of G . e = v ) ) );

:: deftheorem Def2 defines Edges_Out GRAPH_3:def 2 :
for G being Graph
for v being Vertex of G
for X being set
for b4 being Subset of the carrier' of G holds
( b4 = Edges_Out (v,X) iff for e being set holds
( e in b4 iff ( e in the carrier' of G & e in X & the Source of G . e = v ) ) );

definition
let G be Graph;
let v be Vertex of G;
let X be set ;
func Edges_At (v,X) -> Subset of the carrier' of G equals :: GRAPH_3:def 3
(Edges_In (v,X)) \/ (Edges_Out (v,X));
correctness
coherence
(Edges_In (v,X)) \/ (Edges_Out (v,X)) is Subset of the carrier' of G
;
;
end;

:: deftheorem defines Edges_At GRAPH_3:def 3 :
for G being Graph
for v being Vertex of G
for X being set holds Edges_At (v,X) = (Edges_In (v,X)) \/ (Edges_Out (v,X));

registration
let G be finite Graph;
let v be Vertex of G;
let X be set ;
cluster Edges_In (v,X) -> finite ;
correctness
coherence
Edges_In (v,X) is finite
;
proof end;
cluster Edges_Out (v,X) -> finite ;
correctness
coherence
Edges_Out (v,X) is finite
;
proof end;
cluster Edges_At (v,X) -> finite ;
correctness
coherence
Edges_At (v,X) is finite
;
;
end;

registration
let G be Graph;
let v be Vertex of G;
let X be empty set ;
cluster Edges_In (v,X) -> empty ;
correctness
coherence
Edges_In (v,X) is empty
;
proof end;
cluster Edges_Out (v,X) -> empty ;
correctness
coherence
Edges_Out (v,X) is empty
;
proof end;
cluster Edges_At (v,X) -> empty ;
correctness
coherence
Edges_At (v,X) is empty
;
;
end;

definition
let G be Graph;
let v be Vertex of G;
func Edges_In v -> Subset of the carrier' of G equals :: GRAPH_3:def 4
Edges_In (v, the carrier' of G);
correctness
coherence
Edges_In (v, the carrier' of G) is Subset of the carrier' of G
;
;
func Edges_Out v -> Subset of the carrier' of G equals :: GRAPH_3:def 5
Edges_Out (v, the carrier' of G);
correctness
coherence
Edges_Out (v, the carrier' of G) is Subset of the carrier' of G
;
;
end;

:: deftheorem defines Edges_In GRAPH_3:def 4 :
for G being Graph
for v being Vertex of G holds Edges_In v = Edges_In (v, the carrier' of G);

:: deftheorem defines Edges_Out GRAPH_3:def 5 :
for G being Graph
for v being Vertex of G holds Edges_Out v = Edges_Out (v, the carrier' of G);

theorem Th20: :: GRAPH_3:20
for G being Graph
for v being Vertex of G
for X being set holds Edges_In (v,X) c= Edges_In v
proof end;

theorem Th21: :: GRAPH_3:21
for G being Graph
for v being Vertex of G
for X being set holds Edges_Out (v,X) c= Edges_Out v
proof end;

registration
let G be finite Graph;
let v be Vertex of G;
cluster Edges_In v -> finite ;
correctness
coherence
Edges_In v is finite
;
;
cluster Edges_Out v -> finite ;
correctness
coherence
Edges_Out v is finite
;
;
end;

theorem Th22: :: GRAPH_3:22
for G being finite Graph
for v being Vertex of G holds card (Edges_In v) = EdgesIn v
proof end;

theorem Th23: :: GRAPH_3:23
for G being finite Graph
for v being Vertex of G holds card (Edges_Out v) = EdgesOut v
proof end;

definition
let G be finite Graph;
let v be Vertex of G;
let X be set ;
func Degree (v,X) -> Element of NAT equals :: GRAPH_3:def 6
(card (Edges_In (v,X))) + (card (Edges_Out (v,X)));
correctness
coherence
(card (Edges_In (v,X))) + (card (Edges_Out (v,X))) is Element of NAT
;
;
end;

:: deftheorem defines Degree GRAPH_3:def 6 :
for G being finite Graph
for v being Vertex of G
for X being set holds Degree (v,X) = (card (Edges_In (v,X))) + (card (Edges_Out (v,X)));

theorem Th24: :: GRAPH_3:24
for G being finite Graph
for v being Vertex of G holds Degree v = Degree (v, the carrier' of G)
proof end;

theorem Th25: :: GRAPH_3:25
for X being set
for G being finite Graph
for v being Vertex of G st Degree (v,X) <> 0 holds
not Edges_At (v,X) is empty
proof end;

theorem Th26: :: GRAPH_3:26
for e, X being set
for G being finite Graph
for v being Vertex of G st e in the carrier' of G & not e in X & ( v = the Target of G . e or v = the Source of G . e ) holds
Degree v <> Degree (v,X)
proof end;

theorem Th27: :: GRAPH_3:27
for G being finite Graph
for v being Vertex of G
for X2, X1 being set st X2 c= X1 holds
card (Edges_In (v,(X1 \ X2))) = (card (Edges_In (v,X1))) - (card (Edges_In (v,X2)))
proof end;

theorem Th28: :: GRAPH_3:28
for G being finite Graph
for v being Vertex of G
for X2, X1 being set st X2 c= X1 holds
card (Edges_Out (v,(X1 \ X2))) = (card (Edges_Out (v,X1))) - (card (Edges_Out (v,X2)))
proof end;

theorem Th29: :: GRAPH_3:29
for G being finite Graph
for v being Vertex of G
for X2, X1 being set st X2 c= X1 holds
Degree (v,(X1 \ X2)) = (Degree (v,X1)) - (Degree (v,X2))
proof end;

theorem Th30: :: GRAPH_3:30
for X being set
for G being finite Graph
for v being Vertex of G holds
( Edges_In (v,X) = Edges_In (v,(X /\ the carrier' of G)) & Edges_Out (v,X) = Edges_Out (v,(X /\ the carrier' of G)) )
proof end;

theorem Th31: :: GRAPH_3:31
for X being set
for G being finite Graph
for v being Vertex of G holds Degree (v,X) = Degree (v,(X /\ the carrier' of G))
proof end;

theorem Th32: :: GRAPH_3:32
for G being finite Graph
for v being Vertex of G
for c being Chain of G
for vs being FinSequence of the carrier of G st not c is empty & vs is_vertex_seq_of c holds
( v in rng vs iff Degree (v,(rng c)) <> 0 )
proof end;

theorem Th33: :: GRAPH_3:33
for G being non void connected finite Graph
for v being Vertex of G holds Degree v <> 0
proof end;

begin

definition
let G be Graph;
let v1, v2 be Vertex of G;
func AddNewEdge (v1,v2) -> strict Graph means :Def7: :: GRAPH_3:def 7
( the carrier of it = the carrier of G & the carrier' of it = the carrier' of G \/ { the carrier' of G} & the Source of it = the Source of G +* ( the carrier' of G .--> v1) & the Target of it = the Target of G +* ( the carrier' of G .--> v2) );
existence
ex b1 being strict Graph st
( the carrier of b1 = the carrier of G & the carrier' of b1 = the carrier' of G \/ { the carrier' of G} & the Source of b1 = the Source of G +* ( the carrier' of G .--> v1) & the Target of b1 = the Target of G +* ( the carrier' of G .--> v2) )
proof end;
uniqueness
for b1, b2 being strict Graph st the carrier of b1 = the carrier of G & the carrier' of b1 = the carrier' of G \/ { the carrier' of G} & the Source of b1 = the Source of G +* ( the carrier' of G .--> v1) & the Target of b1 = the Target of G +* ( the carrier' of G .--> v2) & the carrier of b2 = the carrier of G & the carrier' of b2 = the carrier' of G \/ { the carrier' of G} & the Source of b2 = the Source of G +* ( the carrier' of G .--> v1) & the Target of b2 = the Target of G +* ( the carrier' of G .--> v2) holds
b1 = b2
;
end;

:: deftheorem Def7 defines AddNewEdge GRAPH_3:def 7 :
for G being Graph
for v1, v2 being Vertex of G
for b4 being strict Graph holds
( b4 = AddNewEdge (v1,v2) iff ( the carrier of b4 = the carrier of G & the carrier' of b4 = the carrier' of G \/ { the carrier' of G} & the Source of b4 = the Source of G +* ( the carrier' of G .--> v1) & the Target of b4 = the Target of G +* ( the carrier' of G .--> v2) ) );

registration
let G be finite Graph;
let v1, v2 be Vertex of G;
cluster AddNewEdge (v1,v2) -> strict finite ;
coherence
AddNewEdge (v1,v2) is finite
proof end;
end;

theorem Th34: :: GRAPH_3:34
for G being Graph
for v1, v2 being Vertex of G holds
( the carrier' of G in the carrier' of (AddNewEdge (v1,v2)) & the carrier' of G = the carrier' of (AddNewEdge (v1,v2)) \ { the carrier' of G} & the Source of (AddNewEdge (v1,v2)) . the carrier' of G = v1 & the Target of (AddNewEdge (v1,v2)) . the carrier' of G = v2 )
proof end;

theorem Th35: :: GRAPH_3:35
for e being set
for G being Graph
for v1, v2 being Vertex of G st e in the carrier' of G holds
( the Source of (AddNewEdge (v1,v2)) . e = the Source of G . e & the Target of (AddNewEdge (v1,v2)) . e = the Target of G . e )
proof end;

theorem Th36: :: GRAPH_3:36
for G being Graph
for v1, v2 being Vertex of G
for c being Chain of G
for vs being FinSequence of the carrier of G
for vs9 being FinSequence of the carrier of (AddNewEdge (v1,v2)) st vs9 = vs & vs is_vertex_seq_of c holds
vs9 is_vertex_seq_of c
proof end;

theorem Th37: :: GRAPH_3:37
for G being Graph
for v1, v2 being Vertex of G
for c being Chain of G holds c is Chain of AddNewEdge (v1,v2)
proof end;

theorem :: GRAPH_3:38
for G being Graph
for v1, v2 being Vertex of G
for p being Path of G holds p is Path of AddNewEdge (v1,v2) by Th37;

theorem Th39: :: GRAPH_3:39
for X being set
for G being Graph
for v1, v2 being Vertex of G
for v9 being Vertex of (AddNewEdge (v1,v2)) st v9 = v1 & v1 <> v2 holds
Edges_In (v9,X) = Edges_In (v1,X)
proof end;

theorem Th40: :: GRAPH_3:40
for X being set
for G being Graph
for v2, v1 being Vertex of G
for v9 being Vertex of (AddNewEdge (v1,v2)) st v9 = v2 & v1 <> v2 holds
Edges_Out (v9,X) = Edges_Out (v2,X)
proof end;

theorem Th41: :: GRAPH_3:41
for X being set
for G being Graph
for v2, v1 being Vertex of G
for v9 being Vertex of (AddNewEdge (v1,v2)) st v9 = v1 & the carrier' of G in X holds
( Edges_Out (v9,X) = (Edges_Out (v1,X)) \/ { the carrier' of G} & Edges_Out (v1,X) misses { the carrier' of G} )
proof end;

theorem Th42: :: GRAPH_3:42
for X being set
for G being Graph
for v1, v2 being Vertex of G
for v9 being Vertex of (AddNewEdge (v1,v2)) st v9 = v2 & the carrier' of G in X holds
( Edges_In (v9,X) = (Edges_In (v2,X)) \/ { the carrier' of G} & Edges_In (v2,X) misses { the carrier' of G} )
proof end;

theorem Th43: :: GRAPH_3:43
for X being set
for G being Graph
for v1, v, v2 being Vertex of G
for v9 being Vertex of (AddNewEdge (v1,v2)) st v9 = v & v <> v2 holds
Edges_In (v9,X) = Edges_In (v,X)
proof end;

theorem Th44: :: GRAPH_3:44
for X being set
for G being Graph
for v2, v, v1 being Vertex of G
for v9 being Vertex of (AddNewEdge (v1,v2)) st v9 = v & v <> v1 holds
Edges_Out (v9,X) = Edges_Out (v,X)
proof end;

theorem Th45: :: GRAPH_3:45
for G being Graph
for v1, v2 being Vertex of G
for p9 being Path of AddNewEdge (v1,v2) st not the carrier' of G in rng p9 holds
p9 is Path of G
proof end;

theorem Th46: :: GRAPH_3:46
for G being Graph
for v1, v2 being Vertex of G
for vs being FinSequence of the carrier of G
for p9 being Path of AddNewEdge (v1,v2)
for vs9 being FinSequence of the carrier of (AddNewEdge (v1,v2)) st not the carrier' of G in rng p9 & vs = vs9 & vs9 is_vertex_seq_of p9 holds
vs is_vertex_seq_of p9
proof end;

registration
let G be connected Graph;
let v1, v2 be Vertex of G;
cluster AddNewEdge (v1,v2) -> strict connected ;
coherence
AddNewEdge (v1,v2) is connected
proof end;
end;

theorem Th47: :: GRAPH_3:47
for X being set
for G being finite Graph
for v, v1, v2 being Vertex of G
for v9 being Vertex of (AddNewEdge (v1,v2)) st v9 = v & v1 <> v2 & ( v = v1 or v = v2 ) & the carrier' of G in X holds
Degree (v9,X) = (Degree (v,X)) + 1
proof end;

theorem Th48: :: GRAPH_3:48
for X being set
for G being finite Graph
for v, v1, v2 being Vertex of G
for v9 being Vertex of (AddNewEdge (v1,v2)) st v9 = v & v <> v1 & v <> v2 holds
Degree (v9,X) = Degree (v,X)
proof end;

begin

Lm4: for G being finite Graph
for c being cyclic Path of G
for vs being FinSequence of the carrier of G
for v being Vertex of G st vs is_vertex_seq_of c & v in rng vs holds
Degree (v,(rng c)) is even

proof end;

theorem Th49: :: GRAPH_3:49
for G being finite Graph
for v being Vertex of G
for c being cyclic Path of G holds Degree (v,(rng c)) is even
proof end;

theorem Th50: :: GRAPH_3:50
for G being finite Graph
for v being Vertex of G
for vs being FinSequence of the carrier of G
for c being Path of G st not c is cyclic & vs is_vertex_seq_of c holds
( Degree (v,(rng c)) is even iff ( v <> vs . 1 & v <> vs . (len vs) ) )
proof end;

definition
let G be Graph;
func G -CycleSet -> FinSequenceSet of the carrier' of G means :Def8: :: GRAPH_3:def 8
for x being set holds
( x in it iff x is cyclic Path of G );
existence
ex b1 being FinSequenceSet of the carrier' of G st
for x being set holds
( x in b1 iff x is cyclic Path of G )
proof end;
uniqueness
for b1, b2 being FinSequenceSet of the carrier' of G st ( for x being set holds
( x in b1 iff x is cyclic Path of G ) ) & ( for x being set holds
( x in b2 iff x is cyclic Path of G ) ) holds
b1 = b2
proof end;
end;

:: deftheorem Def8 defines -CycleSet GRAPH_3:def 8 :
for G being Graph
for b2 being FinSequenceSet of the carrier' of G holds
( b2 = G -CycleSet iff for x being set holds
( x in b2 iff x is cyclic Path of G ) );

theorem Th51: :: GRAPH_3:51
for G being Graph holds {} in G -CycleSet
proof end;

registration
let G be Graph;
cluster G -CycleSet -> non empty ;
coherence
not G -CycleSet is empty
by Th51;
end;

theorem Th52: :: GRAPH_3:52
for G being Graph
for v being Vertex of G
for c being Element of G -CycleSet st v in G -VSet (rng c) holds
{ c9 where c9 is Element of G -CycleSet : ( rng c9 = rng c & ex vs being FinSequence of the carrier of G st
( vs is_vertex_seq_of c9 & vs . 1 = v ) )
}
is non empty Subset of (G -CycleSet)
proof end;

definition
let G be Graph;
let v be Vertex of G;
let c be Element of G -CycleSet ;
assume A1: v in G -VSet (rng c) ;
func Rotate (c,v) -> Element of G -CycleSet equals :Def9: :: GRAPH_3:def 9
choose { c9 where c9 is Element of G -CycleSet : ( rng c9 = rng c & ex vs being FinSequence of the carrier of G st
( vs is_vertex_seq_of c9 & vs . 1 = v ) )
}
;
coherence
choose { c9 where c9 is Element of G -CycleSet : ( rng c9 = rng c & ex vs being FinSequence of the carrier of G st
( vs is_vertex_seq_of c9 & vs . 1 = v ) )
}
is Element of G -CycleSet
proof end;
end;

:: deftheorem Def9 defines Rotate GRAPH_3:def 9 :
for G being Graph
for v being Vertex of G
for c being Element of G -CycleSet st v in G -VSet (rng c) holds
Rotate (c,v) = choose { c9 where c9 is Element of G -CycleSet : ( rng c9 = rng c & ex vs being FinSequence of the carrier of G st
( vs is_vertex_seq_of c9 & vs . 1 = v ) )
}
;

Lm5: for G being Graph
for c being Element of G -CycleSet
for v being Vertex of G st v in G -VSet (rng c) holds
rng (Rotate (c,v)) = rng c

proof end;

definition
let G be Graph;
let c1, c2 be Element of G -CycleSet ;
assume that
A1: G -VSet (rng c1) meets G -VSet (rng c2) and
A2: rng c1 misses rng c2 ;
func CatCycles (c1,c2) -> Element of G -CycleSet means :Def10: :: GRAPH_3:def 10
ex v being Vertex of G st
( v = choose ((G -VSet (rng c1)) /\ (G -VSet (rng c2))) & it = (Rotate (c1,v)) ^ (Rotate (c2,v)) );
existence
ex b1 being Element of G -CycleSet ex v being Vertex of G st
( v = choose ((G -VSet (rng c1)) /\ (G -VSet (rng c2))) & b1 = (Rotate (c1,v)) ^ (Rotate (c2,v)) )
proof end;
correctness
uniqueness
for b1, b2 being Element of G -CycleSet st ex v being Vertex of G st
( v = choose ((G -VSet (rng c1)) /\ (G -VSet (rng c2))) & b1 = (Rotate (c1,v)) ^ (Rotate (c2,v)) ) & ex v being Vertex of G st
( v = choose ((G -VSet (rng c1)) /\ (G -VSet (rng c2))) & b2 = (Rotate (c1,v)) ^ (Rotate (c2,v)) ) holds
b1 = b2
;
;
end;

:: deftheorem Def10 defines CatCycles GRAPH_3:def 10 :
for G being Graph
for c1, c2 being Element of G -CycleSet st G -VSet (rng c1) meets G -VSet (rng c2) & rng c1 misses rng c2 holds
for b4 being Element of G -CycleSet holds
( b4 = CatCycles (c1,c2) iff ex v being Vertex of G st
( v = choose ((G -VSet (rng c1)) /\ (G -VSet (rng c2))) & b4 = (Rotate (c1,v)) ^ (Rotate (c2,v)) ) );

theorem Th53: :: GRAPH_3:53
for G being Graph
for c1, c2 being Element of G -CycleSet st G -VSet (rng c1) meets G -VSet (rng c2) & rng c1 misses rng c2 & ( c1 <> {} or c2 <> {} ) holds
not CatCycles (c1,c2) is empty
proof end;

definition
let G be finite Graph;
let v be Vertex of G;
let X be set ;
assume A1: Degree (v,X) <> 0 ;
func X -PathSet v -> non empty FinSequenceSet of the carrier' of G equals :Def11: :: GRAPH_3:def 11
{ c where c is Element of X * : ( c is Path of G & not c is empty & ex vs being FinSequence of the carrier of G st
( vs is_vertex_seq_of c & vs . 1 = v ) )
}
;
coherence
{ c where c is Element of X * : ( c is Path of G & not c is empty & ex vs being FinSequence of the carrier of G st
( vs is_vertex_seq_of c & vs . 1 = v ) )
}
is non empty FinSequenceSet of the carrier' of G
proof end;
end;

:: deftheorem Def11 defines -PathSet GRAPH_3:def 11 :
for G being finite Graph
for v being Vertex of G
for X being set st Degree (v,X) <> 0 holds
X -PathSet v = { c where c is Element of X * : ( c is Path of G & not c is empty & ex vs being FinSequence of the carrier of G st
( vs is_vertex_seq_of c & vs . 1 = v ) )
}
;

theorem Th54: :: GRAPH_3:54
for X being set
for G being finite Graph
for v being Vertex of G
for p being Element of X -PathSet v
for Y being finite set st Y = the carrier' of G & Degree (v,X) <> 0 holds
len p <= card Y
proof end;

definition
let G be finite Graph;
let v be Vertex of G;
let X be set ;
assume that
A1: for v being Vertex of G holds Degree (v,X) is even and
A2: Degree (v,X) <> 0 ;
func X -CycleSet v -> non empty Subset of (G -CycleSet) equals :Def12: :: GRAPH_3:def 12
{ c where c is Element of G -CycleSet : ( rng c c= X & not c is empty & ex vs being FinSequence of the carrier of G st
( vs is_vertex_seq_of c & vs . 1 = v ) )
}
;
coherence
{ c where c is Element of G -CycleSet : ( rng c c= X & not c is empty & ex vs being FinSequence of the carrier of G st
( vs is_vertex_seq_of c & vs . 1 = v ) )
}
is non empty Subset of (G -CycleSet)
proof end;
end;

:: deftheorem Def12 defines -CycleSet GRAPH_3:def 12 :
for G being finite Graph
for v being Vertex of G
for X being set st ( for v being Vertex of G holds Degree (v,X) is even ) & Degree (v,X) <> 0 holds
X -CycleSet v = { c where c is Element of G -CycleSet : ( rng c c= X & not c is empty & ex vs being FinSequence of the carrier of G st
( vs is_vertex_seq_of c & vs . 1 = v ) )
}
;

theorem Th55: :: GRAPH_3:55
for X being set
for G being finite Graph
for v being Vertex of G st Degree (v,X) <> 0 & ( for v being Vertex of G holds Degree (v,X) is even ) holds
for c being Element of X -CycleSet v holds
( not c is empty & rng c c= X & v in G -VSet (rng c) )
proof end;

theorem Th56: :: GRAPH_3:56
for G being connected finite Graph
for c being Element of G -CycleSet st rng c <> the carrier' of G & not c is empty holds
{ v9 where v9 is Vertex of G : ( v9 in G -VSet (rng c) & Degree v9 <> Degree (v9,(rng c)) ) } is non empty Subset of the carrier of G
proof end;

definition
let G be connected finite Graph;
let c be Element of G -CycleSet ;
assume that
A1: rng c <> the carrier' of G and
A2: not c is empty ;
func ExtendCycle c -> Element of G -CycleSet means :Def13: :: GRAPH_3:def 13
ex c9 being Element of G -CycleSet ex v being Vertex of G st
( v = choose { v9 where v9 is Vertex of G : ( v9 in G -VSet (rng c) & Degree v9 <> Degree (v9,(rng c)) ) } & c9 = choose (( the carrier' of G \ (rng c)) -CycleSet v) & it = CatCycles (c,c9) );
existence
ex b1, c9 being Element of G -CycleSet ex v being Vertex of G st
( v = choose { v9 where v9 is Vertex of G : ( v9 in G -VSet (rng c) & Degree v9 <> Degree (v9,(rng c)) ) } & c9 = choose (( the carrier' of G \ (rng c)) -CycleSet v) & b1 = CatCycles (c,c9) )
proof end;
uniqueness
for b1, b2 being Element of G -CycleSet st ex c9 being Element of G -CycleSet ex v being Vertex of G st
( v = choose { v9 where v9 is Vertex of G : ( v9 in G -VSet (rng c) & Degree v9 <> Degree (v9,(rng c)) ) } & c9 = choose (( the carrier' of G \ (rng c)) -CycleSet v) & b1 = CatCycles (c,c9) ) & ex c9 being Element of G -CycleSet ex v being Vertex of G st
( v = choose { v9 where v9 is Vertex of G : ( v9 in G -VSet (rng c) & Degree v9 <> Degree (v9,(rng c)) ) } & c9 = choose (( the carrier' of G \ (rng c)) -CycleSet v) & b2 = CatCycles (c,c9) ) holds
b1 = b2
;
end;

:: deftheorem Def13 defines ExtendCycle GRAPH_3:def 13 :
for G being connected finite Graph
for c being Element of G -CycleSet st rng c <> the carrier' of G & not c is empty holds
for b3 being Element of G -CycleSet holds
( b3 = ExtendCycle c iff ex c9 being Element of G -CycleSet ex v being Vertex of G st
( v = choose { v9 where v9 is Vertex of G : ( v9 in G -VSet (rng c) & Degree v9 <> Degree (v9,(rng c)) ) } & c9 = choose (( the carrier' of G \ (rng c)) -CycleSet v) & b3 = CatCycles (c,c9) ) );

theorem Th57: :: GRAPH_3:57
for G being connected finite Graph
for c being Element of G -CycleSet st rng c <> the carrier' of G & not c is empty & ( for v being Vertex of G holds Degree v is even ) holds
( not ExtendCycle c is empty & card (rng c) < card (rng (ExtendCycle c)) )
proof end;

begin

definition
let G be Graph;
let p be Path of G;
attr p is Eulerian means :Def14: :: GRAPH_3:def 14
rng p = the carrier' of G;
end;

:: deftheorem Def14 defines Eulerian GRAPH_3:def 14 :
for G being Graph
for p being Path of G holds
( p is Eulerian iff rng p = the carrier' of G );

theorem Th58: :: GRAPH_3:58
for G being connected Graph
for p being Path of G
for vs being FinSequence of the carrier of G st p is Eulerian & vs is_vertex_seq_of p holds
rng vs = the carrier of G
proof end;

theorem Th59: :: GRAPH_3:59
for G being connected finite Graph holds
( ex p being cyclic Path of G st p is Eulerian iff for v being Vertex of G holds Degree v is even )
proof end;

theorem :: GRAPH_3:60
for G being connected finite Graph holds
( ex p being Path of G st
( not p is cyclic & p is Eulerian ) iff ex v1, v2 being Vertex of G st
( v1 <> v2 & ( for v being Vertex of G holds
( Degree v is even iff ( v <> v1 & v <> v2 ) ) ) ) )
proof end;