![]() |
Metamath Proof Explorer |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > MPE Home > Th. List > eupth2lemb | Structured version Visualization version GIF version |
Description: Lemma for eupth2 27605 (induction basis): There are no vertices of odd degree in an Eulerian path of length 0, having no edge and identical endpoints (the single vertex of the Eulerian path). Formerly part of proof for eupth2 27605. (Contributed by Mario Carneiro, 8-Apr-2015.) (Revised by AV, 26-Feb-2021.) |
Ref | Expression |
---|---|
eupth2.v | ⊢ 𝑉 = (Vtx‘𝐺) |
eupth2.i | ⊢ 𝐼 = (iEdg‘𝐺) |
eupth2.g | ⊢ (𝜑 → 𝐺 ∈ UPGraph) |
eupth2.f | ⊢ (𝜑 → Fun 𝐼) |
eupth2.p | ⊢ (𝜑 → 𝐹(EulerPaths‘𝐺)𝑃) |
Ref | Expression |
---|---|
eupth2lemb | ⊢ (𝜑 → {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)‘𝑥)} = ∅) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | 2z 11737 | . . . . . 6 ⊢ 2 ∈ ℤ | |
2 | dvds0 15374 | . . . . . 6 ⊢ (2 ∈ ℤ → 2 ∥ 0) | |
3 | 1, 2 | ax-mp 5 | . . . . 5 ⊢ 2 ∥ 0 |
4 | eupth2.v | . . . . . . . . . . . 12 ⊢ 𝑉 = (Vtx‘𝐺) | |
5 | 4 | fvexi 6447 | . . . . . . . . . . 11 ⊢ 𝑉 ∈ V |
6 | eupth2.i | . . . . . . . . . . . . 13 ⊢ 𝐼 = (iEdg‘𝐺) | |
7 | 6 | fvexi 6447 | . . . . . . . . . . . 12 ⊢ 𝐼 ∈ V |
8 | 7 | resex 5680 | . . . . . . . . . . 11 ⊢ (𝐼 ↾ (𝐹 “ (0..^0))) ∈ V |
9 | 5, 8 | pm3.2i 464 | . . . . . . . . . 10 ⊢ (𝑉 ∈ V ∧ (𝐼 ↾ (𝐹 “ (0..^0))) ∈ V) |
10 | opvtxfv 26302 | . . . . . . . . . 10 ⊢ ((𝑉 ∈ V ∧ (𝐼 ↾ (𝐹 “ (0..^0))) ∈ V) → (Vtx‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = 𝑉) | |
11 | 9, 10 | mp1i 13 | . . . . . . . . 9 ⊢ (𝜑 → (Vtx‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = 𝑉) |
12 | 11 | eqcomd 2831 | . . . . . . . 8 ⊢ (𝜑 → 𝑉 = (Vtx‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)) |
13 | 12 | eleq2d 2892 | . . . . . . 7 ⊢ (𝜑 → (𝑥 ∈ 𝑉 ↔ 𝑥 ∈ (Vtx‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉))) |
14 | 13 | biimpa 470 | . . . . . 6 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑉) → 𝑥 ∈ (Vtx‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)) |
15 | opiedgfv 26305 | . . . . . . . . 9 ⊢ ((𝑉 ∈ V ∧ (𝐼 ↾ (𝐹 “ (0..^0))) ∈ V) → (iEdg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = (𝐼 ↾ (𝐹 “ (0..^0)))) | |
16 | 9, 15 | mp1i 13 | . . . . . . . 8 ⊢ (𝜑 → (iEdg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = (𝐼 ↾ (𝐹 “ (0..^0)))) |
17 | fzo0 12787 | . . . . . . . . . . . 12 ⊢ (0..^0) = ∅ | |
18 | 17 | imaeq2i 5705 | . . . . . . . . . . 11 ⊢ (𝐹 “ (0..^0)) = (𝐹 “ ∅) |
19 | ima0 5722 | . . . . . . . . . . 11 ⊢ (𝐹 “ ∅) = ∅ | |
20 | 18, 19 | eqtri 2849 | . . . . . . . . . 10 ⊢ (𝐹 “ (0..^0)) = ∅ |
21 | 20 | reseq2i 5626 | . . . . . . . . 9 ⊢ (𝐼 ↾ (𝐹 “ (0..^0))) = (𝐼 ↾ ∅) |
22 | res0 5633 | . . . . . . . . 9 ⊢ (𝐼 ↾ ∅) = ∅ | |
23 | 21, 22 | eqtri 2849 | . . . . . . . 8 ⊢ (𝐼 ↾ (𝐹 “ (0..^0))) = ∅ |
24 | 16, 23 | syl6eq 2877 | . . . . . . 7 ⊢ (𝜑 → (iEdg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = ∅) |
25 | 24 | adantr 474 | . . . . . 6 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑉) → (iEdg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = ∅) |
26 | eqid 2825 | . . . . . . 7 ⊢ (Vtx‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = (Vtx‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) | |
27 | eqid 2825 | . . . . . . 7 ⊢ (iEdg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = (iEdg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) | |
28 | 26, 27 | vtxdg0e 26772 | . . . . . 6 ⊢ ((𝑥 ∈ (Vtx‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) ∧ (iEdg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = ∅) → ((VtxDeg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)‘𝑥) = 0) |
29 | 14, 25, 28 | syl2anc 579 | . . . . 5 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑉) → ((VtxDeg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)‘𝑥) = 0) |
30 | 3, 29 | syl5breqr 4911 | . . . 4 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑉) → 2 ∥ ((VtxDeg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)‘𝑥)) |
31 | 30 | notnotd 141 | . . 3 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑉) → ¬ ¬ 2 ∥ ((VtxDeg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)‘𝑥)) |
32 | 31 | ralrimiva 3175 | . 2 ⊢ (𝜑 → ∀𝑥 ∈ 𝑉 ¬ ¬ 2 ∥ ((VtxDeg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)‘𝑥)) |
33 | rabeq0 4186 | . 2 ⊢ ({𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)‘𝑥)} = ∅ ↔ ∀𝑥 ∈ 𝑉 ¬ ¬ 2 ∥ ((VtxDeg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)‘𝑥)) | |
34 | 32, 33 | sylibr 226 | 1 ⊢ (𝜑 → {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)‘𝑥)} = ∅) |
Colors of variables: wff setvar class |
Syntax hints: ¬ wn 3 → wi 4 ∧ wa 386 = wceq 1656 ∈ wcel 2164 ∀wral 3117 {crab 3121 Vcvv 3414 ∅c0 4144 〈cop 4403 class class class wbr 4873 ↾ cres 5344 “ cima 5345 Fun wfun 6117 ‘cfv 6123 (class class class)co 6905 0cc0 10252 2c2 11406 ℤcz 11704 ..^cfzo 12760 ∥ cdvds 15357 Vtxcvtx 26294 iEdgciedg 26295 UPGraphcupgr 26378 VtxDegcvtxdg 26763 EulerPathsceupth 27562 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1894 ax-4 1908 ax-5 2009 ax-6 2075 ax-7 2112 ax-8 2166 ax-9 2173 ax-10 2192 ax-11 2207 ax-12 2220 ax-13 2389 ax-ext 2803 ax-rep 4994 ax-sep 5005 ax-nul 5013 ax-pow 5065 ax-pr 5127 ax-un 7209 ax-cnex 10308 ax-resscn 10309 ax-1cn 10310 ax-icn 10311 ax-addcl 10312 ax-addrcl 10313 ax-mulcl 10314 ax-mulrcl 10315 ax-mulcom 10316 ax-addass 10317 ax-mulass 10318 ax-distr 10319 ax-i2m1 10320 ax-1ne0 10321 ax-1rid 10322 ax-rnegex 10323 ax-rrecex 10324 ax-cnre 10325 ax-pre-lttri 10326 ax-pre-lttrn 10327 ax-pre-ltadd 10328 ax-pre-mulgt0 10329 |
This theorem depends on definitions: df-bi 199 df-an 387 df-or 879 df-3or 1112 df-3an 1113 df-tru 1660 df-ex 1879 df-nf 1883 df-sb 2068 df-mo 2605 df-eu 2640 df-clab 2812 df-cleq 2818 df-clel 2821 df-nfc 2958 df-ne 3000 df-nel 3103 df-ral 3122 df-rex 3123 df-reu 3124 df-rab 3126 df-v 3416 df-sbc 3663 df-csb 3758 df-dif 3801 df-un 3803 df-in 3805 df-ss 3812 df-pss 3814 df-nul 4145 df-if 4307 df-pw 4380 df-sn 4398 df-pr 4400 df-tp 4402 df-op 4404 df-uni 4659 df-int 4698 df-iun 4742 df-br 4874 df-opab 4936 df-mpt 4953 df-tr 4976 df-id 5250 df-eprel 5255 df-po 5263 df-so 5264 df-fr 5301 df-we 5303 df-xp 5348 df-rel 5349 df-cnv 5350 df-co 5351 df-dm 5352 df-rn 5353 df-res 5354 df-ima 5355 df-pred 5920 df-ord 5966 df-on 5967 df-lim 5968 df-suc 5969 df-iota 6086 df-fun 6125 df-fn 6126 df-f 6127 df-f1 6128 df-fo 6129 df-f1o 6130 df-fv 6131 df-riota 6866 df-ov 6908 df-oprab 6909 df-mpt2 6910 df-om 7327 df-1st 7428 df-2nd 7429 df-wrecs 7672 df-recs 7734 df-rdg 7772 df-1o 7826 df-er 8009 df-en 8223 df-dom 8224 df-sdom 8225 df-fin 8226 df-card 9078 df-pnf 10393 df-mnf 10394 df-xr 10395 df-ltxr 10396 df-le 10397 df-sub 10587 df-neg 10588 df-nn 11351 df-2 11414 df-n0 11619 df-z 11705 df-uz 11969 df-xadd 12233 df-fz 12620 df-fzo 12761 df-hash 13411 df-dvds 15358 df-vtx 26296 df-iedg 26297 df-vtxdg 26764 |
This theorem is referenced by: eupth2 27605 |
Copyright terms: Public domain | W3C validator |