let n be non zero Nat; for P1, P2 being n -vertex Path-like _Graph holds P2 is P1 -isomorphic
let P1, P2 be n -vertex Path-like _Graph; P2 is P1 -isomorphic
consider P7 being vertex-distinct Path of P1 such that
A1:
( P7 .vertices() = the_Vertices_of P1 & P7 .edges() = the_Edges_of P1 )
and
( Endvertices P1 = {(P7 .first()),(P7 .last())} iff not P1 is _trivial )
and
( P7 is trivial iff P1 is _trivial )
and
( P7 is closed iff P1 is _trivial )
and
P7 is minlength
by Th31;
consider P8 being vertex-distinct Path of P2 such that
A4:
( P8 .vertices() = the_Vertices_of P2 & P8 .edges() = the_Edges_of P2 )
and
( Endvertices P2 = {(P8 .first()),(P8 .last())} iff not P2 is _trivial )
and
( P8 is trivial iff P2 is _trivial )
and
( P8 is closed iff P2 is _trivial )
and
P8 is minlength
by Th31;
set p1 = P7 .vertexSeq() ;
set p2 = P8 .vertexSeq() ;
( P1 .order() = n & P2 .order() = n )
by GLIB_013:def 3;
then A7:
card (the_Vertices_of P1) = card (the_Vertices_of P2)
;
set f = (P8 .vertexSeq()) * ((P7 .vertexSeq()) ");
A8: card (P8 .vertexSeq()) =
card (dom (P8 .vertexSeq()))
by CARD_1:62
.=
card (the_Vertices_of P2)
by A4, CARD_1:70
.=
card (dom (P7 .vertexSeq()))
by A1, A7, CARD_1:70
.=
card (P7 .vertexSeq())
by CARD_1:62
;
A9: dom (P8 .vertexSeq()) =
Seg (len (P8 .vertexSeq()))
by FINSEQ_1:def 3
.=
dom (P7 .vertexSeq())
by A8, FINSEQ_1:def 3
;
then A10:
dom (P8 .vertexSeq()) = rng ((P7 .vertexSeq()) ")
by FUNCT_1:33;
then A11: dom ((P8 .vertexSeq()) * ((P7 .vertexSeq()) ")) =
dom ((P7 .vertexSeq()) ")
by RELAT_1:27
.=
the_Vertices_of P1
by A1, FUNCT_1:33
;
A12:
len (P7 .vertexSeq()) = len (P8 .vertexSeq())
by A9, FINSEQ_3:29;
A13:
rng ((P8 .vertexSeq()) * ((P7 .vertexSeq()) ")) = the_Vertices_of P2
by A4, A10, RELAT_1:28;
then reconsider f = (P8 .vertexSeq()) * ((P7 .vertexSeq()) ") as Function of (the_Vertices_of P1),(the_Vertices_of P2) by A11, FUNCT_2:1;
now for v, w, e being object st v in dom f & w in dom f & e Joins v,w,P1 holds
ex e9 being object st e9 Joins f . v,f . w,P2let v,
w,
e be
object ;
( v in dom f & w in dom f & e Joins v,w,P1 implies ex e9 being object st b4 Joins f . e9,f . b2,P2 )assume A14:
(
v in dom f &
w in dom f &
e Joins v,
w,
P1 )
;
ex e9 being object st b4 Joins f . e9,f . b2,P2then A15:
v in P7 .vertices()
by A1;
A16:
w in P7 .vertices()
by A1, A14;
consider n being
odd Element of
NAT such that A17:
(
n <= len P7 &
P7 . n = v )
by A15, GLIB_001:87;
consider m being
odd Element of
NAT such that A18:
(
m <= len P7 &
P7 . m = w )
by A16, GLIB_001:87;
set i =
(n + 1) div 2;
set j =
(m + 1) div 2;
A19:
(
(2 * ((n + 1) div 2)) - 1
= n & 1
<= (n + 1) div 2 &
(n + 1) div 2
<= len (P7 .vertexSeq()) )
by A17, GLIB_001:68;
then A20:
(P7 .vertexSeq()) . ((n + 1) div 2) = v
by A17, GLIB_001:def 14;
A21:
(n + 1) div 2
in dom (P7 .vertexSeq())
by A19, FINSEQ_3:25;
A22:
f . v =
(P8 .vertexSeq()) . (((P7 .vertexSeq()) ") . v)
by A14, FUNCT_1:12
.=
(P8 .vertexSeq()) . ((n + 1) div 2)
by A20, A21, FUNCT_1:34
.=
P8 . n
by A12, A19, GLIB_001:def 14
;
A23:
(
(2 * ((m + 1) div 2)) - 1
= m & 1
<= (m + 1) div 2 &
(m + 1) div 2
<= len (P7 .vertexSeq()) )
by A18, GLIB_001:68;
then A24:
(P7 .vertexSeq()) . ((m + 1) div 2) = w
by A18, GLIB_001:def 14;
A25:
(m + 1) div 2
in dom (P7 .vertexSeq())
by A23, FINSEQ_3:25;
A26:
f . w =
(P8 .vertexSeq()) . (((P7 .vertexSeq()) ") . w)
by A14, FUNCT_1:12
.=
(P8 .vertexSeq()) . ((m + 1) div 2)
by A24, A25, FUNCT_1:34
.=
P8 . m
by A12, A23, GLIB_001:def 14
;
( 2
* (len (P7 .vertexSeq())) = (len P7) + 1 & 2
* (len (P8 .vertexSeq())) = (len P8) + 1 )
by GLIB_001:def 14;
then A27:
len P7 = len P8
by A12;
e in P7 .edges()
by A1, A14, GLIB_000:def 13;
then consider k being
odd Element of
NAT such that A28:
(
k < len P7 &
P7 . (k + 1) = e )
by GLIB_001:100;
A29:
(
k <= len P7 &
k + 2
<= len P7 )
by A28, CHORD:4;
e Joins P7 . k,
P7 . (k + 2),
P1
by A28, GLIB_001:def 3;
per cases then
( ( P7 . k = P7 . n & P7 . (k + 2) = P7 . m ) or ( P7 . k = P7 . m & P7 . (k + 2) = P7 . n ) )
by A17, A18, A14, GLIB_000:15;
suppose
(
P7 . k = P7 . n &
P7 . (k + 2) = P7 . m )
;
ex e9 being object st b4 Joins f . e9,f . b2,P2then
(
k = n &
k + 2
= m )
by A17, A18, A29, GLIB_001:def 29;
then A30:
n + 2
= m
;
A31:
n < len P8
reconsider e9 =
P8 . (n + 1) as
object ;
take e9 =
e9;
e9 Joins f . v,f . w,P2
e9 Joins f . v,
P8 . (n + 2),
P2
by A22, A31, GLIB_001:def 3;
hence
e9 Joins f . v,
f . w,
P2
by A30, A26;
verum end; suppose
(
P7 . k = P7 . m &
P7 . (k + 2) = P7 . n )
;
ex e9 being object st b4 Joins f . e9,f . b2,P2then
(
k = m &
k + 2
= n )
by A17, A18, A29, GLIB_001:def 29;
then A33:
m + 2
= n
;
A34:
m < len P8
reconsider e9 =
P8 . (m + 1) as
object ;
take e9 =
e9;
e9 Joins f . v,f . w,P2
e9 Joins P8 . m,
P8 . (m + 2),
P2
by A34, GLIB_001:def 3;
hence
e9 Joins f . v,
f . w,
P2
by A26, A33, A22, GLIB_000:14;
verum end; end; end;
then reconsider f = f as PVertexMapping of P1,P2 by GLIB_011:1;
now for v, w, e9 being object st v in dom f & w in dom f & e9 Joins f . v,f . w,P2 holds
ex e being object st e Joins v,w,P1let v,
w,
e9 be
object ;
( v in dom f & w in dom f & e9 Joins f . v,f . w,P2 implies ex e being object st b4 Joins e,b2,P1 )assume A36:
(
v in dom f &
w in dom f &
e9 Joins f . v,
f . w,
P2 )
;
ex e being object st b4 Joins e,b2,P1then A37:
f . v in P8 .vertices()
by A4, GLIB_000:13;
A38:
f . w in P8 .vertices()
by A4, A36, GLIB_000:13;
consider n being
odd Element of
NAT such that A39:
(
n <= len P8 &
P8 . n = f . v )
by A37, GLIB_001:87;
consider m being
odd Element of
NAT such that A40:
(
m <= len P8 &
P8 . m = f . w )
by A38, GLIB_001:87;
set i =
(n + 1) div 2;
set j =
(m + 1) div 2;
A41:
(
(2 * ((n + 1) div 2)) - 1
= n & 1
<= (n + 1) div 2 &
(n + 1) div 2
<= len (P8 .vertexSeq()) )
by A39, GLIB_001:68;
then A42:
(P8 .vertexSeq()) . ((n + 1) div 2) = f . v
by A39, GLIB_001:def 14;
A43:
(n + 1) div 2
in dom (P8 .vertexSeq())
by A41, FINSEQ_3:25;
A44:
v =
(f ") . ((P8 .vertexSeq()) . ((n + 1) div 2))
by A36, A42, FUNCT_1:34
.=
((((P7 .vertexSeq()) ") ") * ((P8 .vertexSeq()) ")) . ((P8 .vertexSeq()) . ((n + 1) div 2))
by FUNCT_1:44
.=
((P7 .vertexSeq()) * ((P8 .vertexSeq()) ")) . ((P8 .vertexSeq()) . ((n + 1) div 2))
by FUNCT_1:43
.=
(((P7 .vertexSeq()) * ((P8 .vertexSeq()) ")) * (P8 .vertexSeq())) . ((n + 1) div 2)
by A43, FUNCT_1:13
.=
((P7 .vertexSeq()) * (((P8 .vertexSeq()) ") * (P8 .vertexSeq()))) . ((n + 1) div 2)
by RELAT_1:36
.=
((P7 .vertexSeq()) * (id (dom (P8 .vertexSeq())))) . ((n + 1) div 2)
by FUNCT_1:39
.=
(P7 .vertexSeq()) . ((n + 1) div 2)
by A9, RELAT_1:52
.=
P7 . n
by A12, A41, GLIB_001:def 14
;
A45:
(
(2 * ((m + 1) div 2)) - 1
= m & 1
<= (m + 1) div 2 &
(m + 1) div 2
<= len (P8 .vertexSeq()) )
by A40, GLIB_001:68;
then A46:
(P8 .vertexSeq()) . ((m + 1) div 2) = f . w
by A40, GLIB_001:def 14;
A47:
(m + 1) div 2
in dom (P8 .vertexSeq())
by A45, FINSEQ_3:25;
A48:
w =
(f ") . ((P8 .vertexSeq()) . ((m + 1) div 2))
by A36, A46, FUNCT_1:34
.=
((((P7 .vertexSeq()) ") ") * ((P8 .vertexSeq()) ")) . ((P8 .vertexSeq()) . ((m + 1) div 2))
by FUNCT_1:44
.=
((P7 .vertexSeq()) * ((P8 .vertexSeq()) ")) . ((P8 .vertexSeq()) . ((m + 1) div 2))
by FUNCT_1:43
.=
(((P7 .vertexSeq()) * ((P8 .vertexSeq()) ")) * (P8 .vertexSeq())) . ((m + 1) div 2)
by A47, FUNCT_1:13
.=
((P7 .vertexSeq()) * (((P8 .vertexSeq()) ") * (P8 .vertexSeq()))) . ((m + 1) div 2)
by RELAT_1:36
.=
((P7 .vertexSeq()) * (id (dom (P8 .vertexSeq())))) . ((m + 1) div 2)
by FUNCT_1:39
.=
(P7 .vertexSeq()) . ((m + 1) div 2)
by A9, RELAT_1:52
.=
P7 . m
by A12, A45, GLIB_001:def 14
;
( 2
* (len (P8 .vertexSeq())) = (len P8) + 1 & 2
* (len (P7 .vertexSeq())) = (len P7) + 1 )
by GLIB_001:def 14;
then A49:
len P7 = len P8
by A12;
e9 in P8 .edges()
by A4, A36, GLIB_000:def 13;
then consider k being
odd Element of
NAT such that A50:
(
k < len P8 &
P8 . (k + 1) = e9 )
by GLIB_001:100;
A51:
(
k <= len P8 &
k + 2
<= len P8 )
by A50, CHORD:4;
e9 Joins P8 . k,
P8 . (k + 2),
P2
by A50, GLIB_001:def 3;
per cases then
( ( P8 . k = P8 . n & P8 . (k + 2) = P8 . m ) or ( P8 . k = P8 . m & P8 . (k + 2) = P8 . n ) )
by A39, A40, A36, GLIB_000:15;
suppose
(
P8 . k = P8 . n &
P8 . (k + 2) = P8 . m )
;
ex e being object st b4 Joins e,b2,P1then
(
k = n &
k + 2
= m )
by A39, A40, A51, GLIB_001:def 29;
then A52:
n + 2
= m
;
A53:
n < len P7
reconsider e =
P7 . (n + 1) as
object ;
take e =
e;
e Joins v,w,P1
e Joins P7 . n,
P7 . (n + 2),
P1
by A53, GLIB_001:def 3;
hence
e Joins v,
w,
P1
by A44, A52, A48;
verum end; suppose
(
P8 . k = P8 . m &
P8 . (k + 2) = P8 . n )
;
ex e being object st b4 Joins e,b2,P1then
(
k = m &
k + 2
= n )
by A39, A40, A51, GLIB_001:def 29;
then A55:
m + 2
= n
;
A56:
m < len P7
reconsider e =
P7 . (m + 1) as
object ;
take e =
e;
e Joins v,w,P1
e Joins P7 . m,
P7 . (m + 2),
P1
by A56, GLIB_001:def 3;
hence
e Joins v,
w,
P1
by A48, A55, A44, GLIB_000:14;
verum end; end; end;
then A58:
f is continuous
by GLIB_011:2;
( f is total & f is onto )
by A13, FUNCT_2:def 3;
hence
P2 is P1 -isomorphic
by A58, GLIB_011:49; verum