Description: Define the set of all paths (in an undirected graph).
According to Wikipedia ("Path (graph theory)", https://en.wikipedia.org/wiki/Path_(graph_theory) , 3-Oct-2017): "A path is a trail in which all vertices (except possibly the first and last) are distinct. ... use the term simple path to refer to a path which contains no repeated vertices."
According to Bollobas: "... a path is a walk with distinct vertices.", see Notation of Bollobas p. 5. (A walk with distinct vertices is actually a simple path, see upgrwlkdvspth ).
Therefore, a path can be represented by an injective mapping f from { 1 , ... , n } and a mapping p from { 0 , ... , n }, which is injective restricted to the set { 1 , ... , n }, where f enumerates the (indices of the) different edges, and p enumerates the vertices. So the path is also represented by the following sequence: p(0) e(f(1)) p(1) e(f(2)) ... p(n-1) e(f(n)) p(n). (Contributed by Alexander van der Vekens and Mario Carneiro, 4-Oct-2017) (Revised by AV, 9-Jan-2021)
| Ref | Expression | ||
|---|---|---|---|
| Assertion | df-pths | ⊢ Paths = ( 𝑔 ∈ V ↦ { ⟨ 𝑓 , 𝑝 ⟩ ∣ ( 𝑓 ( Trails ‘ 𝑔 ) 𝑝 ∧ Fun ◡ ( 𝑝 ↾ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) ∧ ( ( 𝑝 “ { 0 , ( ♯ ‘ 𝑓 ) } ) ∩ ( 𝑝 “ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) ) = ∅ ) } ) |
| Step | Hyp | Ref | Expression |
|---|---|---|---|
| 0 | cpths | ⊢ Paths | |
| 1 | vg | ⊢ 𝑔 | |
| 2 | cvv | ⊢ V | |
| 3 | vf | ⊢ 𝑓 | |
| 4 | vp | ⊢ 𝑝 | |
| 5 | 3 | cv | ⊢ 𝑓 |
| 6 | ctrls | ⊢ Trails | |
| 7 | 1 | cv | ⊢ 𝑔 |
| 8 | 7 6 | cfv | ⊢ ( Trails ‘ 𝑔 ) |
| 9 | 4 | cv | ⊢ 𝑝 |
| 10 | 5 9 8 | wbr | ⊢ 𝑓 ( Trails ‘ 𝑔 ) 𝑝 |
| 11 | c1 | ⊢ 1 | |
| 12 | cfzo | ⊢ ..^ | |
| 13 | chash | ⊢ ♯ | |
| 14 | 5 13 | cfv | ⊢ ( ♯ ‘ 𝑓 ) |
| 15 | 11 14 12 | co | ⊢ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) |
| 16 | 9 15 | cres | ⊢ ( 𝑝 ↾ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) |
| 17 | 16 | ccnv | ⊢ ◡ ( 𝑝 ↾ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) |
| 18 | 17 | wfun | ⊢ Fun ◡ ( 𝑝 ↾ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) |
| 19 | cc0 | ⊢ 0 | |
| 20 | 19 14 | cpr | ⊢ { 0 , ( ♯ ‘ 𝑓 ) } |
| 21 | 9 20 | cima | ⊢ ( 𝑝 “ { 0 , ( ♯ ‘ 𝑓 ) } ) |
| 22 | 9 15 | cima | ⊢ ( 𝑝 “ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) |
| 23 | 21 22 | cin | ⊢ ( ( 𝑝 “ { 0 , ( ♯ ‘ 𝑓 ) } ) ∩ ( 𝑝 “ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) ) |
| 24 | c0 | ⊢ ∅ | |
| 25 | 23 24 | wceq | ⊢ ( ( 𝑝 “ { 0 , ( ♯ ‘ 𝑓 ) } ) ∩ ( 𝑝 “ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) ) = ∅ |
| 26 | 10 18 25 | w3a | ⊢ ( 𝑓 ( Trails ‘ 𝑔 ) 𝑝 ∧ Fun ◡ ( 𝑝 ↾ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) ∧ ( ( 𝑝 “ { 0 , ( ♯ ‘ 𝑓 ) } ) ∩ ( 𝑝 “ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) ) = ∅ ) |
| 27 | 26 3 4 | copab | ⊢ { ⟨ 𝑓 , 𝑝 ⟩ ∣ ( 𝑓 ( Trails ‘ 𝑔 ) 𝑝 ∧ Fun ◡ ( 𝑝 ↾ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) ∧ ( ( 𝑝 “ { 0 , ( ♯ ‘ 𝑓 ) } ) ∩ ( 𝑝 “ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) ) = ∅ ) } |
| 28 | 1 2 27 | cmpt | ⊢ ( 𝑔 ∈ V ↦ { ⟨ 𝑓 , 𝑝 ⟩ ∣ ( 𝑓 ( Trails ‘ 𝑔 ) 𝑝 ∧ Fun ◡ ( 𝑝 ↾ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) ∧ ( ( 𝑝 “ { 0 , ( ♯ ‘ 𝑓 ) } ) ∩ ( 𝑝 “ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) ) = ∅ ) } ) |
| 29 | 0 28 | wceq | ⊢ Paths = ( 𝑔 ∈ V ↦ { ⟨ 𝑓 , 𝑝 ⟩ ∣ ( 𝑓 ( Trails ‘ 𝑔 ) 𝑝 ∧ Fun ◡ ( 𝑝 ↾ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) ∧ ( ( 𝑝 “ { 0 , ( ♯ ‘ 𝑓 ) } ) ∩ ( 𝑝 “ ( 1 ..^ ( ♯ ‘ 𝑓 ) ) ) ) = ∅ ) } ) |