MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  eupth2lems Structured version   Visualization version   GIF version

Theorem eupth2lems 29185
Description: Lemma for eupth2 29186 (induction step): The only vertices of odd degree in a graph with an Eulerian path are the endpoints, and then only if the endpoints are distinct, if the Eulerian path shortened by one edge has this property. Formerly part of proof for eupth2 29186. (Contributed by Mario Carneiro, 8-Apr-2015.) (Revised by AV, 26-Feb-2021.)
Hypotheses
Ref Expression
eupth2.v 𝑉 = (Vtxβ€˜πΊ)
eupth2.i 𝐼 = (iEdgβ€˜πΊ)
eupth2.g (πœ‘ β†’ 𝐺 ∈ UPGraph)
eupth2.f (πœ‘ β†’ Fun 𝐼)
eupth2.p (πœ‘ β†’ 𝐹(EulerPathsβ€˜πΊ)𝑃)
Assertion
Ref Expression
eupth2lems ((πœ‘ ∧ 𝑛 ∈ β„•0) β†’ ((𝑛 ≀ (β™―β€˜πΉ) β†’ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)})) β†’ ((𝑛 + 1) ≀ (β™―β€˜πΉ) β†’ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜(𝑛 + 1)), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))}))))
Distinct variable groups:   πœ‘,π‘₯   π‘₯,𝐹   π‘₯,𝐼   π‘₯,𝑉   π‘₯,𝑛
Allowed substitution hints:   πœ‘(𝑛)   𝑃(π‘₯,𝑛)   𝐹(𝑛)   𝐺(π‘₯,𝑛)   𝐼(𝑛)   𝑉(𝑛)

Proof of Theorem eupth2lems
Dummy variable 𝑦 is distinct from all other variables.
StepHypRef Expression
1 nn0re 12423 . . . . . 6 (𝑛 ∈ β„•0 β†’ 𝑛 ∈ ℝ)
21adantl 483 . . . . 5 ((πœ‘ ∧ 𝑛 ∈ β„•0) β†’ 𝑛 ∈ ℝ)
32lep1d 12087 . . . 4 ((πœ‘ ∧ 𝑛 ∈ β„•0) β†’ 𝑛 ≀ (𝑛 + 1))
4 peano2re 11329 . . . . . 6 (𝑛 ∈ ℝ β†’ (𝑛 + 1) ∈ ℝ)
52, 4syl 17 . . . . 5 ((πœ‘ ∧ 𝑛 ∈ β„•0) β†’ (𝑛 + 1) ∈ ℝ)
6 eupth2.p . . . . . . . 8 (πœ‘ β†’ 𝐹(EulerPathsβ€˜πΊ)𝑃)
7 eupthiswlk 29159 . . . . . . . 8 (𝐹(EulerPathsβ€˜πΊ)𝑃 β†’ 𝐹(Walksβ€˜πΊ)𝑃)
8 wlkcl 28566 . . . . . . . 8 (𝐹(Walksβ€˜πΊ)𝑃 β†’ (β™―β€˜πΉ) ∈ β„•0)
96, 7, 83syl 18 . . . . . . 7 (πœ‘ β†’ (β™―β€˜πΉ) ∈ β„•0)
109nn0red 12475 . . . . . 6 (πœ‘ β†’ (β™―β€˜πΉ) ∈ ℝ)
1110adantr 482 . . . . 5 ((πœ‘ ∧ 𝑛 ∈ β„•0) β†’ (β™―β€˜πΉ) ∈ ℝ)
12 letr 11250 . . . . 5 ((𝑛 ∈ ℝ ∧ (𝑛 + 1) ∈ ℝ ∧ (β™―β€˜πΉ) ∈ ℝ) β†’ ((𝑛 ≀ (𝑛 + 1) ∧ (𝑛 + 1) ≀ (β™―β€˜πΉ)) β†’ 𝑛 ≀ (β™―β€˜πΉ)))
132, 5, 11, 12syl3anc 1372 . . . 4 ((πœ‘ ∧ 𝑛 ∈ β„•0) β†’ ((𝑛 ≀ (𝑛 + 1) ∧ (𝑛 + 1) ≀ (β™―β€˜πΉ)) β†’ 𝑛 ≀ (β™―β€˜πΉ)))
143, 13mpand 694 . . 3 ((πœ‘ ∧ 𝑛 ∈ β„•0) β†’ ((𝑛 + 1) ≀ (β™―β€˜πΉ) β†’ 𝑛 ≀ (β™―β€˜πΉ)))
1514imim1d 82 . 2 ((πœ‘ ∧ 𝑛 ∈ β„•0) β†’ ((𝑛 ≀ (β™―β€˜πΉ) β†’ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)})) β†’ ((𝑛 + 1) ≀ (β™―β€˜πΉ) β†’ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))))
16 fveq2 6843 . . . . . . . . 9 (π‘₯ = 𝑦 β†’ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘₯) = ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘¦))
1716breq2d 5118 . . . . . . . 8 (π‘₯ = 𝑦 β†’ (2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘₯) ↔ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘¦)))
1817notbid 318 . . . . . . 7 (π‘₯ = 𝑦 β†’ (Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘₯) ↔ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘¦)))
1918elrab 3646 . . . . . 6 (𝑦 ∈ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘₯)} ↔ (𝑦 ∈ 𝑉 ∧ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘¦)))
20 eupth2.v . . . . . . . . 9 𝑉 = (Vtxβ€˜πΊ)
21 eupth2.i . . . . . . . . 9 𝐼 = (iEdgβ€˜πΊ)
22 eupth2.g . . . . . . . . . 10 (πœ‘ β†’ 𝐺 ∈ UPGraph)
2322ad3antrrr 729 . . . . . . . . 9 ((((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) ∧ 𝑦 ∈ 𝑉) β†’ 𝐺 ∈ UPGraph)
24 eupth2.f . . . . . . . . . 10 (πœ‘ β†’ Fun 𝐼)
2524ad3antrrr 729 . . . . . . . . 9 ((((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) ∧ 𝑦 ∈ 𝑉) β†’ Fun 𝐼)
266ad3antrrr 729 . . . . . . . . 9 ((((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) ∧ 𝑦 ∈ 𝑉) β†’ 𝐹(EulerPathsβ€˜πΊ)𝑃)
27 eqid 2737 . . . . . . . . 9 βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩ = βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩
28 eqid 2737 . . . . . . . . 9 βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩ = βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩
29 simpr 486 . . . . . . . . . 10 ((πœ‘ ∧ 𝑛 ∈ β„•0) β†’ 𝑛 ∈ β„•0)
3029ad2antrr 725 . . . . . . . . 9 ((((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) ∧ 𝑦 ∈ 𝑉) β†’ 𝑛 ∈ β„•0)
31 simprl 770 . . . . . . . . . 10 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ (𝑛 + 1) ≀ (β™―β€˜πΉ))
3231adantr 482 . . . . . . . . 9 ((((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) ∧ 𝑦 ∈ 𝑉) β†’ (𝑛 + 1) ≀ (β™―β€˜πΉ))
33 simpr 486 . . . . . . . . 9 ((((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) ∧ 𝑦 ∈ 𝑉) β†’ 𝑦 ∈ 𝑉)
34 simplrr 777 . . . . . . . . 9 ((((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) ∧ 𝑦 ∈ 𝑉) β†’ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))
3520, 21, 23, 25, 26, 27, 28, 30, 32, 33, 34eupth2lem3 29183 . . . . . . . 8 ((((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) ∧ 𝑦 ∈ 𝑉) β†’ (Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘¦) ↔ 𝑦 ∈ if((π‘ƒβ€˜0) = (π‘ƒβ€˜(𝑛 + 1)), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))})))
3635pm5.32da 580 . . . . . . 7 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ ((𝑦 ∈ 𝑉 ∧ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘¦)) ↔ (𝑦 ∈ 𝑉 ∧ 𝑦 ∈ if((π‘ƒβ€˜0) = (π‘ƒβ€˜(𝑛 + 1)), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))}))))
37 0elpw 5312 . . . . . . . . . . 11 βˆ… ∈ 𝒫 𝑉
3820wlkepvtx 28611 . . . . . . . . . . . . . . . 16 (𝐹(Walksβ€˜πΊ)𝑃 β†’ ((π‘ƒβ€˜0) ∈ 𝑉 ∧ (π‘ƒβ€˜(β™―β€˜πΉ)) ∈ 𝑉))
3938simpld 496 . . . . . . . . . . . . . . 15 (𝐹(Walksβ€˜πΊ)𝑃 β†’ (π‘ƒβ€˜0) ∈ 𝑉)
406, 7, 393syl 18 . . . . . . . . . . . . . 14 (πœ‘ β†’ (π‘ƒβ€˜0) ∈ 𝑉)
4140ad2antrr 725 . . . . . . . . . . . . 13 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ (π‘ƒβ€˜0) ∈ 𝑉)
4220wlkp 28567 . . . . . . . . . . . . . . . 16 (𝐹(Walksβ€˜πΊ)𝑃 β†’ 𝑃:(0...(β™―β€˜πΉ))βŸΆπ‘‰)
436, 7, 423syl 18 . . . . . . . . . . . . . . 15 (πœ‘ β†’ 𝑃:(0...(β™―β€˜πΉ))βŸΆπ‘‰)
4443ad2antrr 725 . . . . . . . . . . . . . 14 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ 𝑃:(0...(β™―β€˜πΉ))βŸΆπ‘‰)
45 peano2nn0 12454 . . . . . . . . . . . . . . . . . . 19 (𝑛 ∈ β„•0 β†’ (𝑛 + 1) ∈ β„•0)
4645adantl 483 . . . . . . . . . . . . . . . . . 18 ((πœ‘ ∧ 𝑛 ∈ β„•0) β†’ (𝑛 + 1) ∈ β„•0)
4746adantr 482 . . . . . . . . . . . . . . . . 17 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ (𝑛 + 1) ∈ β„•0)
48 nn0uz 12806 . . . . . . . . . . . . . . . . 17 β„•0 = (β„€β‰₯β€˜0)
4947, 48eleqtrdi 2848 . . . . . . . . . . . . . . . 16 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ (𝑛 + 1) ∈ (β„€β‰₯β€˜0))
509ad2antrr 725 . . . . . . . . . . . . . . . . 17 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ (β™―β€˜πΉ) ∈ β„•0)
5150nn0zd 12526 . . . . . . . . . . . . . . . 16 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ (β™―β€˜πΉ) ∈ β„€)
52 elfz5 13434 . . . . . . . . . . . . . . . 16 (((𝑛 + 1) ∈ (β„€β‰₯β€˜0) ∧ (β™―β€˜πΉ) ∈ β„€) β†’ ((𝑛 + 1) ∈ (0...(β™―β€˜πΉ)) ↔ (𝑛 + 1) ≀ (β™―β€˜πΉ)))
5349, 51, 52syl2anc 585 . . . . . . . . . . . . . . 15 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ ((𝑛 + 1) ∈ (0...(β™―β€˜πΉ)) ↔ (𝑛 + 1) ≀ (β™―β€˜πΉ)))
5431, 53mpbird 257 . . . . . . . . . . . . . 14 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ (𝑛 + 1) ∈ (0...(β™―β€˜πΉ)))
5544, 54ffvelcdmd 7037 . . . . . . . . . . . . 13 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ (π‘ƒβ€˜(𝑛 + 1)) ∈ 𝑉)
5641, 55prssd 4783 . . . . . . . . . . . 12 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))} βŠ† 𝑉)
57 prex 5390 . . . . . . . . . . . . 13 {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))} ∈ V
5857elpw 4565 . . . . . . . . . . . 12 ({(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))} ∈ 𝒫 𝑉 ↔ {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))} βŠ† 𝑉)
5956, 58sylibr 233 . . . . . . . . . . 11 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))} ∈ 𝒫 𝑉)
60 ifcl 4532 . . . . . . . . . . 11 ((βˆ… ∈ 𝒫 𝑉 ∧ {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))} ∈ 𝒫 𝑉) β†’ if((π‘ƒβ€˜0) = (π‘ƒβ€˜(𝑛 + 1)), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))}) ∈ 𝒫 𝑉)
6137, 59, 60sylancr 588 . . . . . . . . . 10 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ if((π‘ƒβ€˜0) = (π‘ƒβ€˜(𝑛 + 1)), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))}) ∈ 𝒫 𝑉)
6261elpwid 4570 . . . . . . . . 9 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ if((π‘ƒβ€˜0) = (π‘ƒβ€˜(𝑛 + 1)), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))}) βŠ† 𝑉)
6362sseld 3944 . . . . . . . 8 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ (𝑦 ∈ if((π‘ƒβ€˜0) = (π‘ƒβ€˜(𝑛 + 1)), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))}) β†’ 𝑦 ∈ 𝑉))
6463pm4.71rd 564 . . . . . . 7 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ (𝑦 ∈ if((π‘ƒβ€˜0) = (π‘ƒβ€˜(𝑛 + 1)), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))}) ↔ (𝑦 ∈ 𝑉 ∧ 𝑦 ∈ if((π‘ƒβ€˜0) = (π‘ƒβ€˜(𝑛 + 1)), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))}))))
6536, 64bitr4d 282 . . . . . 6 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ ((𝑦 ∈ 𝑉 ∧ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘¦)) ↔ 𝑦 ∈ if((π‘ƒβ€˜0) = (π‘ƒβ€˜(𝑛 + 1)), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))})))
6619, 65bitrid 283 . . . . 5 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ (𝑦 ∈ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘₯)} ↔ 𝑦 ∈ if((π‘ƒβ€˜0) = (π‘ƒβ€˜(𝑛 + 1)), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))})))
6766eqrdv 2735 . . . 4 (((πœ‘ ∧ 𝑛 ∈ β„•0) ∧ ((𝑛 + 1) ≀ (β™―β€˜πΉ) ∧ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}))) β†’ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜(𝑛 + 1)), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))}))
6867exp32 422 . . 3 ((πœ‘ ∧ 𝑛 ∈ β„•0) β†’ ((𝑛 + 1) ≀ (β™―β€˜πΉ) β†’ ({π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)}) β†’ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜(𝑛 + 1)), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))}))))
6968a2d 29 . 2 ((πœ‘ ∧ 𝑛 ∈ β„•0) β†’ (((𝑛 + 1) ≀ (β™―β€˜πΉ) β†’ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)})) β†’ ((𝑛 + 1) ≀ (β™―β€˜πΉ) β†’ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜(𝑛 + 1)), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))}))))
7015, 69syld 47 1 ((πœ‘ ∧ 𝑛 ∈ β„•0) β†’ ((𝑛 ≀ (β™―β€˜πΉ) β†’ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^𝑛)))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜π‘›), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜π‘›)})) β†’ ((𝑛 + 1) ≀ (β™―β€˜πΉ) β†’ {π‘₯ ∈ 𝑉 ∣ Β¬ 2 βˆ₯ ((VtxDegβ€˜βŸ¨π‘‰, (𝐼 β†Ύ (𝐹 β€œ (0..^(𝑛 + 1))))⟩)β€˜π‘₯)} = if((π‘ƒβ€˜0) = (π‘ƒβ€˜(𝑛 + 1)), βˆ…, {(π‘ƒβ€˜0), (π‘ƒβ€˜(𝑛 + 1))}))))
Colors of variables: wff setvar class
Syntax hints:  Β¬ wn 3   β†’ wi 4   ↔ wb 205   ∧ wa 397   = wceq 1542   ∈ wcel 2107  {crab 3408   βŠ† wss 3911  βˆ…c0 4283  ifcif 4487  π’« cpw 4561  {cpr 4589  βŸ¨cop 4593   class class class wbr 5106   β†Ύ cres 5636   β€œ cima 5637  Fun wfun 6491  βŸΆwf 6493  β€˜cfv 6497  (class class class)co 7358  β„cr 11051  0cc0 11052  1c1 11053   + caddc 11055   ≀ cle 11191  2c2 12209  β„•0cn0 12414  β„€cz 12500  β„€β‰₯cuz 12764  ...cfz 13425  ..^cfzo 13568  β™―chash 14231   βˆ₯ cdvds 16137  Vtxcvtx 27950  iEdgciedg 27951  UPGraphcupgr 28034  VtxDegcvtxdg 28416  Walkscwlks 28547  EulerPathsceupth 29144
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1798  ax-4 1812  ax-5 1914  ax-6 1972  ax-7 2012  ax-8 2109  ax-9 2117  ax-10 2138  ax-11 2155  ax-12 2172  ax-ext 2708  ax-rep 5243  ax-sep 5257  ax-nul 5264  ax-pow 5321  ax-pr 5385  ax-un 7673  ax-cnex 11108  ax-resscn 11109  ax-1cn 11110  ax-icn 11111  ax-addcl 11112  ax-addrcl 11113  ax-mulcl 11114  ax-mulrcl 11115  ax-mulcom 11116  ax-addass 11117  ax-mulass 11118  ax-distr 11119  ax-i2m1 11120  ax-1ne0 11121  ax-1rid 11122  ax-rnegex 11123  ax-rrecex 11124  ax-cnre 11125  ax-pre-lttri 11126  ax-pre-lttrn 11127  ax-pre-ltadd 11128  ax-pre-mulgt0 11129  ax-pre-sup 11130
This theorem depends on definitions:  df-bi 206  df-an 398  df-or 847  df-ifp 1063  df-3or 1089  df-3an 1090  df-tru 1545  df-fal 1555  df-ex 1783  df-nf 1787  df-sb 2069  df-mo 2539  df-eu 2568  df-clab 2715  df-cleq 2729  df-clel 2815  df-nfc 2890  df-ne 2945  df-nel 3051  df-ral 3066  df-rex 3075  df-rmo 3354  df-reu 3355  df-rab 3409  df-v 3448  df-sbc 3741  df-csb 3857  df-dif 3914  df-un 3916  df-in 3918  df-ss 3928  df-pss 3930  df-nul 4284  df-if 4488  df-pw 4563  df-sn 4588  df-pr 4590  df-op 4594  df-uni 4867  df-int 4909  df-iun 4957  df-br 5107  df-opab 5169  df-mpt 5190  df-tr 5224  df-id 5532  df-eprel 5538  df-po 5546  df-so 5547  df-fr 5589  df-we 5591  df-xp 5640  df-rel 5641  df-cnv 5642  df-co 5643  df-dm 5644  df-rn 5645  df-res 5646  df-ima 5647  df-pred 6254  df-ord 6321  df-on 6322  df-lim 6323  df-suc 6324  df-iota 6449  df-fun 6499  df-fn 6500  df-f 6501  df-f1 6502  df-fo 6503  df-f1o 6504  df-fv 6505  df-riota 7314  df-ov 7361  df-oprab 7362  df-mpo 7363  df-om 7804  df-1st 7922  df-2nd 7923  df-frecs 8213  df-wrecs 8244  df-recs 8318  df-rdg 8357  df-1o 8413  df-2o 8414  df-oadd 8417  df-er 8649  df-map 8768  df-pm 8769  df-en 8885  df-dom 8886  df-sdom 8887  df-fin 8888  df-sup 9379  df-inf 9380  df-dju 9838  df-card 9876  df-pnf 11192  df-mnf 11193  df-xr 11194  df-ltxr 11195  df-le 11196  df-sub 11388  df-neg 11389  df-div 11814  df-nn 12155  df-2 12217  df-3 12218  df-n0 12415  df-xnn0 12487  df-z 12501  df-uz 12765  df-rp 12917  df-xadd 13035  df-fz 13426  df-fzo 13569  df-seq 13908  df-exp 13969  df-hash 14232  df-word 14404  df-cj 14985  df-re 14986  df-im 14987  df-sqrt 15121  df-abs 15122  df-dvds 16138  df-vtx 27952  df-iedg 27953  df-edg 28002  df-uhgr 28012  df-ushgr 28013  df-upgr 28036  df-uspgr 28104  df-vtxdg 28417  df-wlks 28550  df-trls 28643  df-eupth 29145
This theorem is referenced by:  eupth2  29186
  Copyright terms: Public domain W3C validator