![]() |
Metamath Proof Explorer |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > MPE Home > Th. List > eupth2lemb | Structured version Visualization version GIF version |
Description: Lemma for eupth2 27660 (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 27660. (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 11766 | . . . . . 6 ⊢ 2 ∈ ℤ | |
2 | dvds0 15414 | . . . . . 6 ⊢ (2 ∈ ℤ → 2 ∥ 0) | |
3 | 1, 2 | ax-mp 5 | . . . . 5 ⊢ 2 ∥ 0 |
4 | eupth2.v | . . . . . . . . . . . 12 ⊢ 𝑉 = (Vtx‘𝐺) | |
5 | 4 | fvexi 6462 | . . . . . . . . . . 11 ⊢ 𝑉 ∈ V |
6 | eupth2.i | . . . . . . . . . . . . 13 ⊢ 𝐼 = (iEdg‘𝐺) | |
7 | 6 | fvexi 6462 | . . . . . . . . . . . 12 ⊢ 𝐼 ∈ V |
8 | 7 | resex 5695 | . . . . . . . . . . 11 ⊢ (𝐼 ↾ (𝐹 “ (0..^0))) ∈ V |
9 | 5, 8 | pm3.2i 464 | . . . . . . . . . 10 ⊢ (𝑉 ∈ V ∧ (𝐼 ↾ (𝐹 “ (0..^0))) ∈ V) |
10 | opvtxfv 26369 | . . . . . . . . . 10 ⊢ ((𝑉 ∈ V ∧ (𝐼 ↾ (𝐹 “ (0..^0))) ∈ V) → (Vtx‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = 𝑉) | |
11 | 9, 10 | mp1i 13 | . . . . . . . . 9 ⊢ (𝜑 → (Vtx‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = 𝑉) |
12 | 11 | eqcomd 2784 | . . . . . . . 8 ⊢ (𝜑 → 𝑉 = (Vtx‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)) |
13 | 12 | eleq2d 2845 | . . . . . . 7 ⊢ (𝜑 → (𝑥 ∈ 𝑉 ↔ 𝑥 ∈ (Vtx‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉))) |
14 | 13 | biimpa 470 | . . . . . 6 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑉) → 𝑥 ∈ (Vtx‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)) |
15 | opiedgfv 26372 | . . . . . . . . 9 ⊢ ((𝑉 ∈ V ∧ (𝐼 ↾ (𝐹 “ (0..^0))) ∈ V) → (iEdg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = (𝐼 ↾ (𝐹 “ (0..^0)))) | |
16 | 9, 15 | mp1i 13 | . . . . . . . 8 ⊢ (𝜑 → (iEdg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = (𝐼 ↾ (𝐹 “ (0..^0)))) |
17 | fzo0 12816 | . . . . . . . . . . . 12 ⊢ (0..^0) = ∅ | |
18 | 17 | imaeq2i 5720 | . . . . . . . . . . 11 ⊢ (𝐹 “ (0..^0)) = (𝐹 “ ∅) |
19 | ima0 5737 | . . . . . . . . . . 11 ⊢ (𝐹 “ ∅) = ∅ | |
20 | 18, 19 | eqtri 2802 | . . . . . . . . . 10 ⊢ (𝐹 “ (0..^0)) = ∅ |
21 | 20 | reseq2i 5641 | . . . . . . . . 9 ⊢ (𝐼 ↾ (𝐹 “ (0..^0))) = (𝐼 ↾ ∅) |
22 | res0 5648 | . . . . . . . . 9 ⊢ (𝐼 ↾ ∅) = ∅ | |
23 | 21, 22 | eqtri 2802 | . . . . . . . 8 ⊢ (𝐼 ↾ (𝐹 “ (0..^0))) = ∅ |
24 | 16, 23 | syl6eq 2830 | . . . . . . 7 ⊢ (𝜑 → (iEdg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = ∅) |
25 | 24 | adantr 474 | . . . . . 6 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑉) → (iEdg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = ∅) |
26 | eqid 2778 | . . . . . . 7 ⊢ (Vtx‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = (Vtx‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) | |
27 | eqid 2778 | . . . . . . 7 ⊢ (iEdg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) = (iEdg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉) | |
28 | 26, 27 | vtxdg0e 26839 | . . . . . 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 4926 | . . . 4 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑉) → 2 ∥ ((VtxDeg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)‘𝑥)) |
31 | 30 | notnotd 141 | . . 3 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑉) → ¬ ¬ 2 ∥ ((VtxDeg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)‘𝑥)) |
32 | 31 | ralrimiva 3148 | . 2 ⊢ (𝜑 → ∀𝑥 ∈ 𝑉 ¬ ¬ 2 ∥ ((VtxDeg‘〈𝑉, (𝐼 ↾ (𝐹 “ (0..^0)))〉)‘𝑥)) |
33 | rabeq0 4187 | . 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 1601 ∈ wcel 2107 ∀wral 3090 {crab 3094 Vcvv 3398 ∅c0 4141 〈cop 4404 class class class wbr 4888 ↾ cres 5359 “ cima 5360 Fun wfun 6131 ‘cfv 6137 (class class class)co 6924 0cc0 10274 2c2 11435 ℤcz 11733 ..^cfzo 12789 ∥ cdvds 15396 Vtxcvtx 26361 iEdgciedg 26362 UPGraphcupgr 26445 VtxDegcvtxdg 26830 EulerPathsceupth 27617 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1839 ax-4 1853 ax-5 1953 ax-6 2021 ax-7 2055 ax-8 2109 ax-9 2116 ax-10 2135 ax-11 2150 ax-12 2163 ax-13 2334 ax-ext 2754 ax-rep 5008 ax-sep 5019 ax-nul 5027 ax-pow 5079 ax-pr 5140 ax-un 7228 ax-cnex 10330 ax-resscn 10331 ax-1cn 10332 ax-icn 10333 ax-addcl 10334 ax-addrcl 10335 ax-mulcl 10336 ax-mulrcl 10337 ax-mulcom 10338 ax-addass 10339 ax-mulass 10340 ax-distr 10341 ax-i2m1 10342 ax-1ne0 10343 ax-1rid 10344 ax-rnegex 10345 ax-rrecex 10346 ax-cnre 10347 ax-pre-lttri 10348 ax-pre-lttrn 10349 ax-pre-ltadd 10350 ax-pre-mulgt0 10351 |
This theorem depends on definitions: df-bi 199 df-an 387 df-or 837 df-3or 1072 df-3an 1073 df-tru 1605 df-ex 1824 df-nf 1828 df-sb 2012 df-mo 2551 df-eu 2587 df-clab 2764 df-cleq 2770 df-clel 2774 df-nfc 2921 df-ne 2970 df-nel 3076 df-ral 3095 df-rex 3096 df-reu 3097 df-rab 3099 df-v 3400 df-sbc 3653 df-csb 3752 df-dif 3795 df-un 3797 df-in 3799 df-ss 3806 df-pss 3808 df-nul 4142 df-if 4308 df-pw 4381 df-sn 4399 df-pr 4401 df-tp 4403 df-op 4405 df-uni 4674 df-int 4713 df-iun 4757 df-br 4889 df-opab 4951 df-mpt 4968 df-tr 4990 df-id 5263 df-eprel 5268 df-po 5276 df-so 5277 df-fr 5316 df-we 5318 df-xp 5363 df-rel 5364 df-cnv 5365 df-co 5366 df-dm 5367 df-rn 5368 df-res 5369 df-ima 5370 df-pred 5935 df-ord 5981 df-on 5982 df-lim 5983 df-suc 5984 df-iota 6101 df-fun 6139 df-fn 6140 df-f 6141 df-f1 6142 df-fo 6143 df-f1o 6144 df-fv 6145 df-riota 6885 df-ov 6927 df-oprab 6928 df-mpt2 6929 df-om 7346 df-1st 7447 df-2nd 7448 df-wrecs 7691 df-recs 7753 df-rdg 7791 df-1o 7845 df-er 8028 df-en 8244 df-dom 8245 df-sdom 8246 df-fin 8247 df-card 9100 df-pnf 10415 df-mnf 10416 df-xr 10417 df-ltxr 10418 df-le 10419 df-sub 10610 df-neg 10611 df-nn 11380 df-2 11443 df-n0 11648 df-z 11734 df-uz 11998 df-xadd 12263 df-fz 12649 df-fzo 12790 df-hash 13442 df-dvds 15397 df-vtx 26363 df-iedg 26364 df-vtxdg 26831 |
This theorem is referenced by: eupth2 27660 |
Copyright terms: Public domain | W3C validator |