:: Vertex sequences induced by chains
:: by Yatsuka Nakamura and Piotr Rudnicki
::
:: Received May 13, 1995
:: Copyright (c) 1995 Association of Mizar Users

begin

theorem Th1: :: GRAPH_2:1

for m, k, n being Nat holds
( ( m + 1 <= k & k <= n ) iff ex i being Element of NAT st
( m <= i & i < n & k = i + 1 ) )

proof end;

theorem Th2: :: GRAPH_2:2

for q, p being FinSequence
for n being Element of NAT st q = p | (Seg n) holds
( len q <= len p & ( for i being Element of NAT st 1 <= i & i <= len q holds
p . i = q . i ) )

proof end;

theorem Th3: :: GRAPH_2:3

for X, Y being set
for k being Element of NAT st X c= Seg k & Y c= dom (Sgm X) holds
(Sgm X) * (Sgm Y) = Sgm (rng ((Sgm X) | Y))

proof end;

Lm1: for m, n being Element of NAT
for F being finite set st F = { k where k is Element of NAT : ( m <= k & k <= m + n ) } holds
card F = n + 1

proof end;

theorem Th4: :: GRAPH_2:4

for m, n being Element of NAT holds card { k where k is Element of NAT : ( m <= k & k <= m + n ) } = n + 1

proof end;

theorem Th5: :: GRAPH_2:5

for n, m, l being Element of NAT st 1 <= l & l <= n holds
(Sgm { kk where kk is Element of NAT : ( m + 1 <= kk & kk <= m + n ) } ) . l = m + l

proof end;

begin

definition

let p be FinSequence;
let m, n be Nat;
func (m,n) -cut p -> FinSequence means :Def1: :: GRAPH_2:def 1
( (len it) + m = n + 1 & ( for i being Nat st i < len it holds
it . (i + 1) = p . (m + i) ) ) if ( 1 <= m & m <= n & n <= len p )
otherwise it = {} ;
consistency
for b₁ being FinSequence holds verum ;
existence
( ( 1 <= m & m <= n & n <= len p implies ex b₁ being FinSequence st
( (len b₁) + m = n + 1 & ( for i being Nat st i < len b₁ holds
b₁ . (i + 1) = p . (m + i) ) ) ) & ( ( not 1 <= m or not m <= n or not n <= len p ) implies ex b₁ being FinSequence st b₁ = {} ) )

proof end;

uniqueness
for b₁, b₂ being FinSequence holds
( ( 1 <= m & m <= n & n <= len p & (len b₁) + m = n + 1 & ( for i being Nat st i < len b₁ holds
b₁ . (i + 1) = p . (m + i) ) & (len b₂) + m = n + 1 & ( for i being Nat st i < len b₂ holds
b₂ . (i + 1) = p . (m + i) ) implies b₁ = b₂ ) & ( ( not 1 <= m or not m <= n or not n <= len p ) & b₁ = {} & b₂ = {} implies b₁ = b₂ ) )

proof end;

end;

:: deftheorem Def1 defines -cut GRAPH_2:def 1 :
for p being FinSequence
for m, n being Nat
for b₄ being FinSequence holds
( ( 1 <= m & m <= n & n <= len p implies ( b₄ = (m,n) -cut p iff ( (len b₄) + m = n + 1 & ( for i being Nat st i < len b₄ holds
b₄ . (i + 1) = p . (m + i) ) ) ) ) & ( ( not 1 <= m or not m <= n or not n <= len p ) implies ( b₄ = (m,n) -cut p iff b₄ = {} ) ) );

Lm2: 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 Th6: :: GRAPH_2:6

for p being FinSequence
for m being Element of NAT st 1 <= m & m <= len p holds
(m,m) -cut p = <*(p . m)*>

proof end;

theorem Th7: :: GRAPH_2:7

for p being FinSequence holds (1,(len p)) -cut p = p

proof end;

theorem Th8: :: GRAPH_2:8

for p being FinSequence
for m, n, r being Element of NAT st m <= n & n <= r & r <= len p holds
(((m + 1),n) -cut p) ^ (((n + 1),r) -cut p) = ((m + 1),r) -cut p

proof end;

theorem :: GRAPH_2:9

for p being FinSequence
for m being Element of NAT st m <= len p holds
((1,m) -cut p) ^ (((m + 1),(len p)) -cut p) = p

proof end;

theorem :: GRAPH_2:10

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

proof end;

theorem Th11: :: GRAPH_2:11

for p being FinSequence
for m, n being Element of NAT holds rng ((m,n) -cut p) c= rng p

proof end;

definition

let D be set ;
let p be FinSequence of D;
let m, n be Nat;
:: original: -cut
redefine func (m,n) -cut p -> FinSequence of D;
coherence
(m,n) -cut p is FinSequence of D

proof end;

end;

theorem Th12: :: GRAPH_2:12

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

proof end;

begin

definition

let p, q be FinSequence;
func p ^' q -> FinSequence equals :: GRAPH_2:def 2
p ^ ((2,(len q)) -cut q);
correctness
coherence
p ^ ((2,(len q)) -cut q) is FinSequence;
;

end;

:: deftheorem defines ^' GRAPH_2:def 2 :
for p, q being FinSequence holds p ^' q = p ^ ((2,(len q)) -cut q);

theorem Th13: :: GRAPH_2:13

for q, p being FinSequence st q <> {} holds
(len (p ^' q)) + 1 = (len p) + (len q)

proof end;

theorem Th14: :: GRAPH_2:14

for p, q being FinSequence
for k being Element of NAT st 1 <= k & k <= len p holds
(p ^' q) . k = p . k

proof end;

theorem Th15: :: GRAPH_2:15

for q, p being FinSequence
for k being Element of NAT st 1 <= k & k < len q holds
(p ^' q) . ((len p) + k) = q . (k + 1)

proof end;

theorem Th16: :: GRAPH_2:16

for q, p being FinSequence st 1 < len q holds
(p ^' q) . (len (p ^' q)) = q . (len q)

proof end;

theorem Th17: :: GRAPH_2:17

for p, q being FinSequence holds rng (p ^' q) c= (rng p) \/ (rng q)

proof end;

definition

let D be set ;
let p, q be FinSequence of D;
:: original: ^'
redefine func p ^' q -> FinSequence of D;
coherence
p ^' q is FinSequence of D

proof end;

end;

theorem :: GRAPH_2:18

for p, q being FinSequence st p <> {} & q <> {} & p . (len p) = q . 1 holds
rng (p ^' q) = (rng p) \/ (rng q)

proof end;

begin

definition

let f be FinSequence;
attr f is TwoValued means :Def3: :: GRAPH_2:def 3
card (rng f) = 2;

end;

:: deftheorem Def3 defines TwoValued GRAPH_2:def 3 :
for f being FinSequence holds
( f is TwoValued iff card (rng f) = 2 );

Lm3: now

set p = <*1,2*>;
2 > 1 ;
hence len <*1,2*> > 1 by FINSEQ_1:61; :: thesis: ( 1 <> 2 & rng <*1,2*> = {1,2} )
thus 1 <> 2 ; :: thesis: rng <*1,2*> = {1,2}
thus rng <*1,2*> = (rng <*1*>) \/ (rng <*2*>) by FINSEQ_1:44
.= {1} \/ (rng <*2*>) by FINSEQ_1:55
.= {1} \/ {2} by FINSEQ_1:55
.= {1,2} by ENUMSET1:41 ; :: thesis: verum

end;

theorem Th19: :: GRAPH_2:19

for p being FinSequence holds
( p is TwoValued iff ( len p > 1 & ex x, y being set st
( x <> y & rng p = {x,y} ) ) )

proof end;

then Lm4: <*1,2*> is TwoValued
by Lm3;

Lm5: now

let i be Nat; :: thesis: ( 1 <= i & i + 1 <= len <*1,2*> implies <*1,2*> . i <> <*1,2*> . (i + 1) )
set p = <*1,2*>;
assume that
A1: 1 <= i and
A2: i + 1 <= len <*1,2*> ; :: thesis: <*1,2*> . i <> <*1,2*> . (i + 1)
i + 1 <= 1 + 1 by A2, FINSEQ_1:61;
then i <= 1 by XREAL_1:8;
then A3: i = 1 by A1, XXREAL_0:1;
then <*1,2*> . i = 1 by FINSEQ_1:61;
hence <*1,2*> . i <> <*1,2*> . (i + 1) by A3, FINSEQ_1:61; :: thesis: verum

end;

definition

let f be FinSequence;
attr f is Alternating means :Def4: :: GRAPH_2:def 4
for i being Nat st 1 <= i & i + 1 <= len f holds
f . i <> f . (i + 1);

end;

:: deftheorem Def4 defines Alternating GRAPH_2:def 4 :
for f being FinSequence holds
( f is Alternating iff for i being Nat st 1 <= i & i + 1 <= len f holds
f . i <> f . (i + 1) );

Lm6: <*1,2*> is Alternating
by Def4, Lm5;

registration

cluster Relation-like Function-like finite FinSequence-like FinSubsequence-like TwoValued Alternating set ;
existence
ex b₁ being FinSequence st
( b₁ is TwoValued & b₁ is Alternating ) by Lm4, Lm6;

end;

theorem Th20: :: GRAPH_2:20

for a1, a2 being TwoValued Alternating FinSequence st len a1 = len a2 & rng a1 = rng a2 & a1 . 1 = a2 . 1 holds
a1 = a2

proof end;

theorem Th21: :: GRAPH_2:21

for a1, a2 being TwoValued Alternating FinSequence st a1 <> a2 & len a1 = len a2 & rng a1 = rng a2 holds
for i being Element of NAT st 1 <= i & i <= len a1 holds
a1 . i <> a2 . i

proof end;

theorem Th22: :: GRAPH_2:22

for a1, a2 being TwoValued Alternating FinSequence st a1 <> a2 & len a1 = len a2 & rng a1 = rng a2 holds
for a being TwoValued Alternating FinSequence st len a = len a1 & rng a = rng a1 & not a = a1 holds
a = a2

proof end;

theorem Th23: :: GRAPH_2:23

for X, Y being set
for n being Element of NAT st X <> Y & n > 1 holds
ex a1 being TwoValued Alternating FinSequence st
( rng a1 = {X,Y} & len a1 = n & a1 . 1 = X )

proof end;

begin

registration

let X be set ;
let fs be FinSequence of X;
cluster -> FinSubsequence-like Element of K21(fs);
coherence
for b₁ being Subset of fs holds b₁ is FinSubsequence-like

proof end;

end;

theorem :: GRAPH_2:24

canceled;

theorem :: GRAPH_2:25

canceled;

theorem Th26: :: GRAPH_2:26

for f being FinSubsequence
for g, h, fg, fh, fgh being FinSequence st rng g c= dom f & rng h c= dom f & fg = f * g & fh = f * h & fgh = f * (g ^ h) holds
fgh = fg ^ fh

proof end;

theorem :: GRAPH_2:27

for X being set
for fs being FinSequence of X
for fss being Subset of fs holds
( dom fss c= dom fs & rng fss c= rng fs ) by RELAT_1:25;

theorem Th28: :: GRAPH_2:28

for X being set
for fs being FinSequence of X holds fs is Subset of fs

proof end;

theorem Th29: :: GRAPH_2:29

for X, Y being set
for fs being FinSequence of X
for fss being Subset of fs holds fss | Y is Subset of fs

proof end;

theorem Th30: :: GRAPH_2:30

for X being set
for fs, fs1, fs2 being FinSequence of X
for fss, fss2 being Subset of fs
for fss1 being Subset of fs1 st Seq fss = fs1 & Seq fss1 = fs2 & fss2 = fss | (rng ((Sgm (dom fss)) | (dom fss1))) holds
Seq fss2 = fs2

proof end;

begin

theorem Th31: :: GRAPH_2:31

for G being Graph
for v1, v2 being Element of G
for e being set st e joins v1,v2 holds
e joins v2,v1

proof end;

theorem Th32: :: GRAPH_2:32

for G being Graph
for v1, v2, v3, v4 being Element of G
for e being set st e joins v1,v2 & e joins v3,v4 & not ( v1 = v3 & v2 = v4 ) holds
( v1 = v4 & v2 = v3 )

proof end;

definition

let G be Graph;
let X be set ;
canceled;
func G -VSet X -> set equals :: GRAPH_2:def 6
{ 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
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;

:: deftheorem GRAPH_2:def 5 :
canceled;

:: deftheorem defines -VSet GRAPH_2:def 6 :
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 ) ) } ;

definition

let G be Graph;
let vs be FinSequence of the carrier of G;
let c be FinSequence;
pred vs is_vertex_seq_of c means :Def7: :: GRAPH_2:def 7
( len vs = (len c) + 1 & ( for n being Element of NAT st 1 <= n & n <= len c holds
c . n joins vs /. n,vs /. (n + 1) ) );

end;

:: deftheorem Def7 defines is_vertex_seq_of GRAPH_2:def 7 :
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 Element of NAT st 1 <= n & n <= len c holds
c . n joins vs /. n,vs /. (n + 1) ) ) );

theorem :: GRAPH_2:33

canceled;

theorem Th34: :: GRAPH_2:34

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

proof end;

theorem Th35: :: GRAPH_2:35

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

proof end;

theorem Th36: :: GRAPH_2:36

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

proof end;

theorem Th37: :: GRAPH_2:37

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 ) ) )

proof end;

definition

let G be Graph;
let c be FinSequence;
pred c alternates_vertices_in G means :Def8: :: GRAPH_2:def 8
( len c >= 1 & card (G -VSet (rng c)) = 2 & ( for n being Element of NAT st n in dom c holds
the Source of G . (c . n) <> the Target of G . (c . n) ) );

end;

:: deftheorem Def8 defines alternates_vertices_in GRAPH_2:def 8 :
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 Element of NAT st n in dom c holds
the Source of G . (c . n) <> the Target of G . (c . n) ) ) );

theorem Th38: :: GRAPH_2:38

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 Element of NAT st k in dom c holds
vs . k <> vs . (k + 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 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 Th40: :: GRAPH_2:40

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

proof end;

theorem Th41: :: GRAPH_2:41

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 ) ) )

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 Th42: :: GRAPH_2:42

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 )

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 ) ) ;
func vertex-seq c -> FinSequence of the carrier of G means :: GRAPH_2:def 9
it is_vertex_seq_of c;
existence
ex b₁ being FinSequence of the carrier of G st b₁ is_vertex_seq_of c by Th36;
uniqueness
for b₁, b₂ being FinSequence of the carrier of G st b₁ is_vertex_seq_of c & b₂ is_vertex_seq_of c holds
b₁ = b₂ by A1, Th42;

end;

:: deftheorem defines vertex-seq GRAPH_2:def 9 :
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₃ being FinSequence of the carrier of G holds
( b₃ = vertex-seq c iff b₃ is_vertex_seq_of c );

theorem Th43: :: GRAPH_2:43

for n being Element of 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

proof end;

theorem Th44: :: GRAPH_2:44

for q being FinSequence
for m, n being Element of 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 Th45: :: GRAPH_2:45

for m, n being Element of 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

proof end;

theorem Th46: :: GRAPH_2:46

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

proof end;

theorem Th47: :: GRAPH_2:47

for G being Graph
for vs1, vs2, vs being FinSequence of the carrier of G
for c1, c2, c 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;

begin

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

proof end;

definition

let G be Graph;
let IT be Chain of G;
attr IT is simple means :Def10: :: GRAPH_2:def 10
ex vs being FinSequence of the carrier of G st
( vs is_vertex_seq_of IT & ( for n, m being Element of NAT st 1 <= n & n < m & m <= len vs & vs . n = vs . m holds
( n = 1 & m = len vs ) ) );

end;

:: deftheorem Def10 defines simple GRAPH_2:def 10 :
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 Element of NAT st 1 <= n & n < m & m <= len vs & vs . n = vs . m holds
( n = 1 & m = len vs ) ) ) );

registration

let G be Graph;
cluster Relation-like NAT -defined the carrier' of G -valued Function-like finite FinSequence-like FinSubsequence-like simple Chain of G;
existence
ex b₁ being Chain of G st b₁ is simple

proof end;

end;

theorem :: GRAPH_2:48

canceled;

theorem :: GRAPH_2:49

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

proof end;

theorem Th50: :: GRAPH_2:50

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

proof end;

theorem :: GRAPH_2:51

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 Element of NAT st 1 <= n & n < m & m <= len vs & vs . n = vs . m holds
( n = 1 & m = len vs )

proof end;

theorem Th52: :: GRAPH_2:52

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 )

proof end;

theorem :: GRAPH_2:53

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) )

proof end;

registration

let G be Graph;
cluster empty -> V7() Chain of G;
correctness
coherence
for b₁ being Chain of G st b₁ is empty holds
b₁ is one-to-one ;
;

end;

theorem :: GRAPH_2:54

for p being FinSequence
for n being Element of 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;
cluster Relation-like NAT -defined the carrier' of G -valued Function-like one-to-one finite FinSequence-like FinSubsequence-like simple Chain of G;
existence
ex b₁ being Path of G st b₁ is simple

proof end;

end;

theorem :: GRAPH_2:55

for G being Graph
for sc being simple Chain of G st 2 < len sc holds
sc is Path of G

proof end;

theorem :: GRAPH_2:56

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 ) )

proof end;

registration

let G be Graph;
cluster empty -> oriented Chain of G;
correctness
coherence
for b₁ being Chain of G st b₁ is empty holds
b₁ is oriented ;
;

end;

definition

let G be Graph;
let oc be oriented Chain of G;
assume A1: oc <> {} ;
func vertex-seq oc -> FinSequence of the carrier of G means :: GRAPH_2:def 11
( it is_vertex_seq_of oc & it . 1 = the Source of G . (oc . 1) );
existence
ex b₁ being FinSequence of the carrier of G st
( b₁ is_vertex_seq_of oc & b₁ . 1 = the Source of G . (oc . 1) )

proof end;

uniqueness
for b₁, b₂ being FinSequence of the carrier of G st b₁ is_vertex_seq_of oc & b₁ . 1 = the Source of G . (oc . 1) & b₂ is_vertex_seq_of oc & b₂ . 1 = the Source of G . (oc . 1) holds
b₁ = b₂ by A1, Th37;

end;

:: deftheorem defines vertex-seq GRAPH_2:def 11 :
for G being Graph
for oc being oriented Chain of G st oc <> {} holds
for b₃ being FinSequence of the carrier of G holds
( b₃ = vertex-seq oc iff ( b₃ is_vertex_seq_of oc & b₃ . 1 = the Source of G . (oc . 1) ) );

begin

theorem :: GRAPH_2:57

for D being non empty set
for f1 being non empty FinSequence of D
for f2 being FinSequence of D holds (f1 ^' f2) /. 1 = f1 /. 1

proof end;

theorem :: GRAPH_2:58

for D being non empty set
for f1 being FinSequence of D
for f2 being non trivial FinSequence of D holds (f1 ^' f2) /. (len (f1 ^' f2)) = f2 /. (len f2)

proof end;

theorem Th59: :: GRAPH_2:59

for f being FinSequence holds f ^' {} = f

proof end;

theorem :: GRAPH_2:60

for x being set
for f being FinSequence holds f ^' <*x*> = f

proof end;

theorem :: GRAPH_2:61

for D being non empty set
for n being Element of NAT
for f1, f2 being FinSequence of D st 1 <= n & n <= len f1 holds
(f1 ^' f2) /. n = f1 /. n

proof end;

theorem :: GRAPH_2:62

for D being non empty set
for n being Element of NAT
for f1, f2 being FinSequence of D st 1 <= n & n < len f2 holds
(f1 ^' f2) /. ((len f1) + n) = f2 /. (n + 1)

proof end;

definition

let F be FinSequence of INT ;
let m, n be Element of NAT ;
assume that
A1: 1 <= m and
A2: m <= n and
A3: n <= len F ;
func min_at (F,m,n) -> Element of NAT means :Def12: :: GRAPH_2:def 12
ex X being non empty finite Subset of INT st
( X = rng ((m,n) -cut F) & it + 1 = ((min X) .. ((m,n) -cut F)) + m );
existence
ex b₁ being Element of NAT ex X being non empty finite Subset of INT st
( X = rng ((m,n) -cut F) & b₁ + 1 = ((min X) .. ((m,n) -cut F)) + m )

proof end;

uniqueness
for b₁, b₂ being Element of NAT st ex X being non empty finite Subset of INT st
( X = rng ((m,n) -cut F) & b₁ + 1 = ((min X) .. ((m,n) -cut F)) + m ) & ex X being non empty finite Subset of INT st
( X = rng ((m,n) -cut F) & b₂ + 1 = ((min X) .. ((m,n) -cut F)) + m ) holds
b₁ = b₂ ;

end;

:: deftheorem Def12 defines min_at GRAPH_2:def 12 :
for F being FinSequence of INT
for m, n being Element of NAT st 1 <= m & m <= n & n <= len F holds
for b₄ being Element of NAT holds
( b₄ = min_at (F,m,n) iff ex X being non empty finite Subset of INT st
( X = rng ((m,n) -cut F) & b₄ + 1 = ((min X) .. ((m,n) -cut F)) + m ) );

theorem Th63: :: GRAPH_2:63

for F being FinSequence of INT
for m, n, ma being Element of NAT st 1 <= m & m <= n & n <= len F holds
( ma = min_at (F,m,n) iff ( m <= ma & ma <= n & ( for i being Element of NAT st m <= i & i <= n holds
F . ma <= F . i ) & ( for i being Element of NAT st m <= i & i < ma holds
F . ma < F . i ) ) )

proof end;

theorem :: GRAPH_2:64

for F being FinSequence of INT
for m being Element of NAT st 1 <= m & m <= len F holds
min_at (F,m,m) = m

proof end;

definition

let F be FinSequence of INT ;
let m, n be Element of NAT ;
pred F is_non_decreasing_on m,n means :Def13: :: GRAPH_2:def 13
for i, j being Element of NAT st m <= i & i <= j & j <= n holds
F . i <= F . j;

end;

:: deftheorem Def13 defines is_non_decreasing_on GRAPH_2:def 13 :
for F being FinSequence of INT
for m, n being Element of NAT holds
( F is_non_decreasing_on m,n iff for i, j being Element of NAT st m <= i & i <= j & j <= n holds
F . i <= F . j );

definition

let F be FinSequence of INT ;
let n be Element of NAT ;
pred F is_split_at n means :Def14: :: GRAPH_2:def 14
for i, j being Element of NAT st 1 <= i & i <= n & n < j & j <= len F holds
F . i <= F . j;

end;

:: deftheorem Def14 defines is_split_at GRAPH_2:def 14 :
for F being FinSequence of INT
for n being Element of NAT holds
( F is_split_at n iff for i, j being Element of NAT st 1 <= i & i <= n & n < j & j <= len F holds
F . i <= F . j );

theorem :: GRAPH_2:65

for F, F1 being FinSequence of INT
for k, ma being Element of NAT st k + 1 <= len F & ma = min_at (F,(k + 1),(len F)) & F is_split_at k & F is_non_decreasing_on 1,k & F1 = (F +* ((k + 1),(F . ma))) +* (ma,(F . (k + 1))) holds
F1 is_non_decreasing_on 1,k + 1

proof end;

theorem :: GRAPH_2:66

for F, F1 being FinSequence of INT
for k, ma being Element of NAT st k + 1 <= len F & ma = min_at (F,(k + 1),(len F)) & F is_split_at k & F1 = (F +* ((k + 1),(F . ma))) +* (ma,(F . (k + 1))) holds
F1 is_split_at k + 1

proof end;