:: by Yatsuka Nakamura and Piotr Rudnicki

::

:: Received May 13, 1995

:: Copyright (c) 1995-2018 Association of Mizar Users

Lm2: for p being FinSequence

for m, n being Nat st 1 <= m & m <= n + 1 & n <= len p holds

( (len ((m,n) -cut p)) + m = n + 1 & ( for i being Nat st i < len ((m,n) -cut p) holds

((m,n) -cut p) . (i + 1) = p . (m + i) ) )

proof end;

canceled;

canceled;

canceled;

canceled;

theorem :: GRAPH_2:29

theorem :: GRAPH_2:30

definition

let G be Graph;

let X be set ;

coherence

{ v where v is Element of G : ex e being Element of the carrier' of G st

( e in X & ( v = the Source of G . e or v = the Target of G . e ) ) } is set ;

;

end;
let X be set ;

func G -VSet X -> set equals :: GRAPH_2:def 1

{ v where v is Element of G : ex e being Element of the carrier' of G st

( e in X & ( v = the Source of G . e or v = the Target of G . e ) ) } ;

correctness { v where v is Element of G : ex e being Element of the carrier' of G st

( e in X & ( v = the Source of G . e or v = the Target of G . e ) ) } ;

coherence

{ v where v is Element of G : ex e being Element of the carrier' of G st

( e in X & ( v = the Source of G . e or v = the Target of G . e ) ) } is set ;

;

:: deftheorem defines -VSet GRAPH_2:def 1 :

for G being Graph

for X being set holds G -VSet X = { v where v is Element of G : ex e being Element of the carrier' of G st

( e in X & ( v = the Source of G . e or v = the Target of G . e ) ) } ;

for G being Graph

for X being set holds G -VSet X = { v where v is Element of G : ex e being Element of the carrier' of G st

( e in X & ( v = the Source of G . e or v = the Target of G . e ) ) } ;

:: deftheorem defines is_vertex_seq_of GRAPH_2:def 2 :

for G being Graph

for vs being FinSequence of the carrier of G

for c being FinSequence holds

( vs is_vertex_seq_of c iff ( len vs = (len c) + 1 & ( for n being Nat st 1 <= n & n <= len c holds

c . n joins vs /. n,vs /. (n + 1) ) ) );

for G being Graph

for vs being FinSequence of the carrier of G

for c being FinSequence holds

( vs is_vertex_seq_of c iff ( len vs = (len c) + 1 & ( for n being Nat st 1 <= n & n <= len c holds

c . n joins vs /. n,vs /. (n + 1) ) ) );

theorem Th31: :: GRAPH_2:31

for G being Graph

for vs being FinSequence of the carrier of G

for c being Chain of G st c <> {} & vs is_vertex_seq_of c holds

G -VSet (rng c) = rng vs

for vs being FinSequence of the carrier of G

for c being Chain of G st c <> {} & vs is_vertex_seq_of c holds

G -VSet (rng c) = rng vs

proof end;

theorem Th33: :: GRAPH_2:33

for G being Graph

for c being Chain of G ex vs being FinSequence of the carrier of G st vs is_vertex_seq_of c

for c being Chain of G ex vs being FinSequence of the carrier of G st vs is_vertex_seq_of c

proof end;

theorem Th34: :: GRAPH_2:34

for G being Graph

for vs1, vs2 being FinSequence of the carrier of G

for c being Chain of G st c <> {} & vs1 is_vertex_seq_of c & vs2 is_vertex_seq_of c & vs1 <> vs2 holds

( vs1 . 1 <> vs2 . 1 & ( for vs being FinSequence of the carrier of G holds

( not vs is_vertex_seq_of c or vs = vs1 or vs = vs2 ) ) )

for vs1, vs2 being FinSequence of the carrier of G

for c being Chain of G st c <> {} & vs1 is_vertex_seq_of c & vs2 is_vertex_seq_of c & vs1 <> vs2 holds

( vs1 . 1 <> vs2 . 1 & ( for vs being FinSequence of the carrier of G holds

( not vs is_vertex_seq_of c or vs = vs1 or vs = vs2 ) ) )

proof end;

:: deftheorem defines alternates_vertices_in GRAPH_2:def 3 :

for G being Graph

for c being FinSequence holds

( c alternates_vertices_in G iff ( len c >= 1 & card (G -VSet (rng c)) = 2 & ( for n being Nat st n in dom c holds

the Source of G . (c . n) <> the Target of G . (c . n) ) ) );

for G being Graph

for c being FinSequence holds

( c alternates_vertices_in G iff ( len c >= 1 & card (G -VSet (rng c)) = 2 & ( for n being Nat st n in dom c holds

the Source of G . (c . n) <> the Target of G . (c . n) ) ) );

theorem Th35: :: GRAPH_2:35

for G being Graph

for vs being FinSequence of the carrier of G

for c being Chain of G st c alternates_vertices_in G & vs is_vertex_seq_of c holds

for k being Nat st k in dom c holds

vs . k <> vs . (k + 1)

for vs being FinSequence of the carrier of G

for c being Chain of G st c alternates_vertices_in G & vs is_vertex_seq_of c holds

for k being Nat st k in dom c holds

vs . k <> vs . (k + 1)

proof end;

theorem Th36: :: GRAPH_2:36

for G being Graph

for vs being FinSequence of the carrier of G

for c being Chain of G st c alternates_vertices_in G & vs is_vertex_seq_of c holds

rng vs = {( the Source of G . (c . 1)),( the Target of G . (c . 1))}

for vs being FinSequence of the carrier of G

for c being Chain of G st c alternates_vertices_in G & vs is_vertex_seq_of c holds

rng vs = {( the Source of G . (c . 1)),( the Target of G . (c . 1))}

proof end;

theorem Th37: :: GRAPH_2:37

for G being Graph

for vs being FinSequence of the carrier of G

for c being Chain of G st c alternates_vertices_in G & vs is_vertex_seq_of c holds

vs is TwoValued Alternating FinSequence

for vs being FinSequence of the carrier of G

for c being Chain of G st c alternates_vertices_in G & vs is_vertex_seq_of c holds

vs is TwoValued Alternating FinSequence

proof end;

theorem Th38: :: GRAPH_2:38

for G being Graph

for c being Chain of G st c alternates_vertices_in G holds

ex vs1, vs2 being FinSequence of the carrier of G st

( vs1 <> vs2 & vs1 is_vertex_seq_of c & vs2 is_vertex_seq_of c & ( for vs being FinSequence of the carrier of G holds

( not vs is_vertex_seq_of c or vs = vs1 or vs = vs2 ) ) )

for c being Chain of G st c alternates_vertices_in G holds

ex vs1, vs2 being FinSequence of the carrier of G st

( vs1 <> vs2 & vs1 is_vertex_seq_of c & vs2 is_vertex_seq_of c & ( for vs being FinSequence of the carrier of G holds

( not vs is_vertex_seq_of c or vs = vs1 or vs = vs2 ) ) )

proof end;

Lm7: for D being non empty set st ( for x, y being set st x in D & y in D holds

x = y ) holds

card D = 1

proof end;

theorem Th39: :: GRAPH_2:39

for G being Graph

for vs being FinSequence of the carrier of G

for c being Chain of G st vs is_vertex_seq_of c holds

( ( card the carrier of G = 1 or ( c <> {} & not c alternates_vertices_in G ) ) iff for vs1 being FinSequence of the carrier of G st vs1 is_vertex_seq_of c holds

vs1 = vs )

for vs being FinSequence of the carrier of G

for c being Chain of G st vs is_vertex_seq_of c holds

( ( card the carrier of G = 1 or ( c <> {} & not c alternates_vertices_in G ) ) iff for vs1 being FinSequence of the carrier of G st vs1 is_vertex_seq_of c holds

vs1 = vs )

proof end;

definition

let G be Graph;

let c be Chain of G;

assume A1: ( card the carrier of G = 1 or ( c <> {} & not c alternates_vertices_in G ) ) ;

existence

ex b_{1} being FinSequence of the carrier of G st b_{1} is_vertex_seq_of c
by Th33;

uniqueness

for b_{1}, b_{2} being FinSequence of the carrier of G st b_{1} is_vertex_seq_of c & b_{2} is_vertex_seq_of c holds

b_{1} = b_{2}
by A1, Th39;

end;
let c be Chain of G;

assume A1: ( card the carrier of G = 1 or ( c <> {} & not c alternates_vertices_in G ) ) ;

existence

ex b

uniqueness

for b

b

:: deftheorem defines vertex-seq GRAPH_2:def 4 :

for G being Graph

for c being Chain of G st ( card the carrier of G = 1 or ( c <> {} & not c alternates_vertices_in G ) ) holds

for b_{3} being FinSequence of the carrier of G holds

( b_{3} = vertex-seq c iff b_{3} is_vertex_seq_of c );

for G being Graph

for c being Chain of G st ( card the carrier of G = 1 or ( c <> {} & not c alternates_vertices_in G ) ) holds

for b

( b

theorem Th40: :: GRAPH_2:40

for n being Nat

for G being Graph

for vs, vs1 being FinSequence of the carrier of G

for c, c1 being Chain of G st vs is_vertex_seq_of c & c1 = c | (Seg n) & vs1 = vs | (Seg (n + 1)) holds

vs1 is_vertex_seq_of c1

for G being Graph

for vs, vs1 being FinSequence of the carrier of G

for c, c1 being Chain of G st vs is_vertex_seq_of c & c1 = c | (Seg n) & vs1 = vs | (Seg (n + 1)) holds

vs1 is_vertex_seq_of c1

proof end;

theorem Th41: :: GRAPH_2:41

for q being FinSequence

for m, n being Nat

for G being Graph

for c being Chain of G st 1 <= m & m <= n & n <= len c & q = (m,n) -cut c holds

q is Chain of G

for m, n being Nat

for G being Graph

for c being Chain of G st 1 <= m & m <= n & n <= len c & q = (m,n) -cut c holds

q is Chain of G

proof end;

theorem Th42: :: GRAPH_2:42

for m, n being Nat

for G being Graph

for vs, vs1 being FinSequence of the carrier of G

for c, c1 being Chain of G st 1 <= m & m <= n & n <= len c & c1 = (m,n) -cut c & vs is_vertex_seq_of c & vs1 = (m,(n + 1)) -cut vs holds

vs1 is_vertex_seq_of c1

for G being Graph

for vs, vs1 being FinSequence of the carrier of G

for c, c1 being Chain of G st 1 <= m & m <= n & n <= len c & c1 = (m,n) -cut c & vs is_vertex_seq_of c & vs1 = (m,(n + 1)) -cut vs holds

vs1 is_vertex_seq_of c1

proof end;

theorem Th43: :: GRAPH_2:43

for G being Graph

for vs1, vs2 being FinSequence of the carrier of G

for c1, c2 being Chain of G st vs1 is_vertex_seq_of c1 & vs2 is_vertex_seq_of c2 & vs1 . (len vs1) = vs2 . 1 holds

c1 ^ c2 is Chain of G

for vs1, vs2 being FinSequence of the carrier of G

for c1, c2 being Chain of G st vs1 is_vertex_seq_of c1 & vs2 is_vertex_seq_of c2 & vs1 . (len vs1) = vs2 . 1 holds

c1 ^ c2 is Chain of G

proof end;

theorem Th44: :: GRAPH_2:44

for G being Graph

for vs, vs1, vs2 being FinSequence of the carrier of G

for c, c1, c2 being Chain of G st vs1 is_vertex_seq_of c1 & vs2 is_vertex_seq_of c2 & vs1 . (len vs1) = vs2 . 1 & c = c1 ^ c2 & vs = vs1 ^' vs2 holds

vs is_vertex_seq_of c

for vs, vs1, vs2 being FinSequence of the carrier of G

for c, c1, c2 being Chain of G st vs1 is_vertex_seq_of c1 & vs2 is_vertex_seq_of c2 & vs1 . (len vs1) = vs2 . 1 & c = c1 ^ c2 & vs = vs1 ^' vs2 holds

vs is_vertex_seq_of c

proof end;

Lm8: for G being Graph

for v being Element of G holds <*v*> is_vertex_seq_of {}

by FINSEQ_1:39;

:: deftheorem Def9 defines simple GRAPH_2:def 5 :

for G being Graph

for IT being Chain of G holds

( IT is simple iff ex vs being FinSequence of the carrier of G st

( vs is_vertex_seq_of IT & ( for n, m being Nat st 1 <= n & n < m & m <= len vs & vs . n = vs . m holds

( n = 1 & m = len vs ) ) ) );

for G being Graph

for IT being Chain of G holds

( IT is simple iff ex vs being FinSequence of the carrier of G st

( vs is_vertex_seq_of IT & ( for n, m being Nat st 1 <= n & n < m & m <= len vs & vs . n = vs . m holds

( n = 1 & m = len vs ) ) ) );

registration

let G be Graph;

ex b_{1} being Chain of G st b_{1} is simple

end;
cluster Relation-like NAT -defined the carrier' of G -valued Function-like finite FinSequence-like FinSubsequence-like simple for of ;

existence ex b

proof end;

theorem :: GRAPH_2:45

for n being Nat

for G being Graph

for sc being simple Chain of G holds sc | (Seg n) is simple Chain of G

for G being Graph

for sc being simple Chain of G holds sc | (Seg n) is simple Chain of G

proof end;

theorem Th46: :: GRAPH_2:46

for G being Graph

for vs1, vs2 being FinSequence of the carrier of G

for sc being simple Chain of G st 2 < len sc & vs1 is_vertex_seq_of sc & vs2 is_vertex_seq_of sc holds

vs1 = vs2

for vs1, vs2 being FinSequence of the carrier of G

for sc being simple Chain of G st 2 < len sc & vs1 is_vertex_seq_of sc & vs2 is_vertex_seq_of sc holds

vs1 = vs2

proof end;

theorem :: GRAPH_2:47

for G being Graph

for vs being FinSequence of the carrier of G

for sc being simple Chain of G st vs is_vertex_seq_of sc holds

for n, m being Nat st 1 <= n & n < m & m <= len vs & vs . n = vs . m holds

( n = 1 & m = len vs )

for vs being FinSequence of the carrier of G

for sc being simple Chain of G st vs is_vertex_seq_of sc holds

for n, m being Nat st 1 <= n & n < m & m <= len vs & vs . n = vs . m holds

( n = 1 & m = len vs )

proof end;

theorem Th48: :: GRAPH_2:48

for G being Graph

for vs being FinSequence of the carrier of G

for c being Chain of G st c is not simple Chain of G & vs is_vertex_seq_of c holds

ex fc being Subset of c ex fvs being Subset of vs ex c1 being Chain of G ex vs1 being FinSequence of the carrier of G st

( len c1 < len c & vs1 is_vertex_seq_of c1 & len vs1 < len vs & vs . 1 = vs1 . 1 & vs . (len vs) = vs1 . (len vs1) & Seq fc = c1 & Seq fvs = vs1 )

for vs being FinSequence of the carrier of G

for c being Chain of G st c is not simple Chain of G & vs is_vertex_seq_of c holds

ex fc being Subset of c ex fvs being Subset of vs ex c1 being Chain of G ex vs1 being FinSequence of the carrier of G st

( len c1 < len c & vs1 is_vertex_seq_of c1 & len vs1 < len vs & vs . 1 = vs1 . 1 & vs . (len vs) = vs1 . (len vs1) & Seq fc = c1 & Seq fvs = vs1 )

proof end;

theorem :: GRAPH_2:49

for G being Graph

for vs being FinSequence of the carrier of G

for c being Chain of G st vs is_vertex_seq_of c holds

ex fc being Subset of c ex fvs being Subset of vs ex sc being simple Chain of G ex vs1 being FinSequence of the carrier of G st

( Seq fc = sc & Seq fvs = vs1 & vs1 is_vertex_seq_of sc & vs . 1 = vs1 . 1 & vs . (len vs) = vs1 . (len vs1) )

for vs being FinSequence of the carrier of G

for c being Chain of G st vs is_vertex_seq_of c holds

ex fc being Subset of c ex fvs being Subset of vs ex sc being simple Chain of G ex vs1 being FinSequence of the carrier of G st

( Seq fc = sc & Seq fvs = vs1 & vs1 is_vertex_seq_of sc & vs . 1 = vs1 . 1 & vs . (len vs) = vs1 . (len vs1) )

proof end;

registration

let G be Graph;

correctness

coherence

for b_{1} being Chain of G st b_{1} is empty holds

b_{1} is V17();

;

end;
correctness

coherence

for b

b

;

theorem :: GRAPH_2:50

for p being FinSequence

for n being Nat

for G being Graph st p is Path of G holds

p | (Seg n) is Path of G

for n being Nat

for G being Graph st p is Path of G holds

p | (Seg n) is Path of G

proof end;

registration

let G be Graph;

ex b_{1} being Path of G st b_{1} is simple

end;
cluster Relation-like NAT -defined the carrier' of G -valued Function-like one-to-one finite FinSequence-like FinSubsequence-like simple for Path of ;

existence ex b

proof end;

theorem :: GRAPH_2:52

for G being Graph

for sc being simple Chain of G holds

( sc is Path of G iff ( len sc = 0 or len sc = 1 or sc . 1 <> sc . 2 ) )

for sc being simple Chain of G holds

( sc is Path of G iff ( len sc = 0 or len sc = 1 or sc . 1 <> sc . 2 ) )

proof end;

registration

let G be Graph;

correctness

coherence

for b_{1} being Chain of G st b_{1} is empty holds

b_{1} is oriented ;

;

end;
correctness

coherence

for b

b

;

definition

let G be Graph;

let oc be oriented Chain of G;

assume A1: oc <> {} ;

ex b_{1} being FinSequence of the carrier of G st

( b_{1} is_vertex_seq_of oc & b_{1} . 1 = the Source of G . (oc . 1) )

for b_{1}, b_{2} being FinSequence of the carrier of G st b_{1} is_vertex_seq_of oc & b_{1} . 1 = the Source of G . (oc . 1) & b_{2} is_vertex_seq_of oc & b_{2} . 1 = the Source of G . (oc . 1) holds

b_{1} = b_{2}
by A1, Th34;

end;
let oc be oriented Chain of G;

assume A1: oc <> {} ;

func vertex-seq oc -> FinSequence of the carrier of G means :: GRAPH_2:def 6

( it is_vertex_seq_of oc & it . 1 = the Source of G . (oc . 1) );

existence ( it is_vertex_seq_of oc & it . 1 = the Source of G . (oc . 1) );

ex b

( b

proof end;

uniqueness for b

b

:: deftheorem defines vertex-seq GRAPH_2:def 6 :

for G being Graph

for oc being oriented Chain of G st oc <> {} holds

for b_{3} being FinSequence of the carrier of G holds

( b_{3} = vertex-seq oc iff ( b_{3} is_vertex_seq_of oc & b_{3} . 1 = the Source of G . (oc . 1) ) );

for G being Graph

for oc being oriented Chain of G st oc <> {} holds

for b

( b

:: The following chain:

:: .--->.

:: ^ |

:: | v

:: .--->.<---.--->.

:: | ^

:: v |

:: .--->.

:: is a case in point: