Theorem eupth2lems 30840

Description: Lemma for eupth2 30841 (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 30841. (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.

Step	Hyp	Ref	Expression
1		nn0re 12616	. . . . . 6 ⊢ (𝑛 ∈ ℕ0 → 𝑛 ∈ ℝ)
2	1	adantl 487	. . . . 5 ⊢ ((𝜑 ∧ 𝑛 ∈ ℕ0) → 𝑛 ∈ ℝ)
3	2	lep1d 12249	. . . 4 ⊢ ((𝜑 ∧ 𝑛 ∈ ℕ0) → 𝑛 ≤ (𝑛 + 1))
4		peano2re 11484	. . . . . 6 ⊢ (𝑛 ∈ ℝ → (𝑛 + 1) ∈ ℝ)
5	2, 4	syl 18	. . . . 5 ⊢ ((𝜑 ∧ 𝑛 ∈ ℕ0) → (𝑛 + 1) ∈ ℝ)
6		eupth2.p	. . . . . . . 8 ⊢ (𝜑 → 𝐹(EulerPaths‘𝐺)𝑃)
7		eupthiswlk 30814	. . . . . . . 8 ⊢ (𝐹(EulerPaths‘𝐺)𝑃 → 𝐹(Walks‘𝐺)𝑃)
8		wlkcl 30197	. . . . . . . 8 ⊢ (𝐹(Walks‘𝐺)𝑃 → (♯‘𝐹) ∈ ℕ0)
9	6, 7, 8	3syl 19	. . . . . . 7 ⊢ (𝜑 → (♯‘𝐹) ∈ ℕ0)
10	9	nn0red 12669	. . . . . 6 ⊢ (𝜑 → (♯‘𝐹) ∈ ℝ)
11	10	adantr 486	. . . . 5 ⊢ ((𝜑 ∧ 𝑛 ∈ ℕ0) → (♯‘𝐹) ∈ ℝ)
12		letr 11405	. . . . 5 ⊢ ((𝑛 ∈ ℝ ∧ (𝑛 + 1) ∈ ℝ ∧ (♯‘𝐹) ∈ ℝ) → ((𝑛 ≤ (𝑛 + 1) ∧ (𝑛 + 1) ≤ (♯‘𝐹)) → 𝑛 ≤ (♯‘𝐹)))
13	2, 5, 11, 12	syl3anc 1398	. . . 4 ⊢ ((𝜑 ∧ 𝑛 ∈ ℕ0) → ((𝑛 ≤ (𝑛 + 1) ∧ (𝑛 + 1) ≤ (♯‘𝐹)) → 𝑛 ≤ (♯‘𝐹)))
14	3, 13	mpand 708	. . 3 ⊢ ((𝜑 ∧ 𝑛 ∈ ℕ0) → ((𝑛 + 1) ≤ (♯‘𝐹) → 𝑛 ≤ (♯‘𝐹)))
15	14	imim1d 83	. 2 ⊢ ((𝜑 ∧ 𝑛 ∈ ℕ0) → ((𝑛 ≤ (♯‘𝐹) → {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)})) → ((𝑛 + 1) ≤ (♯‘𝐹) → {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))))
16		fveq2 6885	. . . . . . . . 9 ⊢ (𝑥 = 𝑦 → ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑥) = ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑦))
17	16	breq2d 5114	. . . . . . . 8 ⊢ (𝑥 = 𝑦 → (2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑥) ↔ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑦)))
18	17	notbid 321	. . . . . . 7 ⊢ (𝑥 = 𝑦 → (¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑥) ↔ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑦)))
19	18	elrab 3644	. . . . . 6 ⊢ (𝑦 ∈ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑥)} ↔ (𝑦 ∈ 𝑉 ∧ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑦)))
20		eupth2.v	. . . . . . . . 9 ⊢ 𝑉 = (Vtx‘𝐺)
21		eupth2.i	. . . . . . . . 9 ⊢ 𝐼 = (iEdg‘𝐺)
22		eupth2.g	. . . . . . . . . 10 ⊢ (𝜑 → 𝐺 ∈ UPGraph)
23	22	ad3antrrr 743	. . . . . . . . 9 ⊢ ((((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) ∧ 𝑦 ∈ 𝑉) → 𝐺 ∈ UPGraph)
24		eupth2.f	. . . . . . . . . 10 ⊢ (𝜑 → Fun 𝐼)
25	24	ad3antrrr 743	. . . . . . . . 9 ⊢ ((((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) ∧ 𝑦 ∈ 𝑉) → Fun 𝐼)
26	6	ad3antrrr 743	. . . . . . . . 9 ⊢ ((((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) ∧ 𝑦 ∈ 𝑉) → 𝐹(EulerPaths‘𝐺)𝑃)
27		eqid 2760	. . . . . . . . 9 ⊢ ⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩ = ⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩
28		eqid 2760	. . . . . . . . 9 ⊢ ⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩ = ⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩
29		simpr 490	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑛 ∈ ℕ0) → 𝑛 ∈ ℕ0)
30	29	ad2antrr 739	. . . . . . . . 9 ⊢ ((((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) ∧ 𝑦 ∈ 𝑉) → 𝑛 ∈ ℕ0)
31		simprl 783	. . . . . . . . . 10 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → (𝑛 + 1) ≤ (♯‘𝐹))
32	31	adantr 486	. . . . . . . . 9 ⊢ ((((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) ∧ 𝑦 ∈ 𝑉) → (𝑛 + 1) ≤ (♯‘𝐹))
33		simpr 490	. . . . . . . . 9 ⊢ ((((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) ∧ 𝑦 ∈ 𝑉) → 𝑦 ∈ 𝑉)
34		simplrr 790	. . . . . . . . 9 ⊢ ((((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) ∧ 𝑦 ∈ 𝑉) → {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))
35	20, 21, 23, 25, 26, 27, 28, 30, 32, 33, 34	eupth2lem3 30838	. . . . . . . 8 ⊢ ((((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) ∧ 𝑦 ∈ 𝑉) → (¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑦) ↔ 𝑦 ∈ if((𝑃‘0) = (𝑃‘(𝑛 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑛 + 1))})))
36	35	pm5.32da 590	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → ((𝑦 ∈ 𝑉 ∧ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑦)) ↔ (𝑦 ∈ 𝑉 ∧ 𝑦 ∈ if((𝑃‘0) = (𝑃‘(𝑛 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑛 + 1))}))))
37		0elpw 5316	. . . . . . . . . . 11 ⊢ ∅ ∈ 𝒫 𝑉
38	20	wlkepvtx 30240	. . . . . . . . . . . . . . . 16 ⊢ (𝐹(Walks‘𝐺)𝑃 → ((𝑃‘0) ∈ 𝑉 ∧ (𝑃‘(♯‘𝐹)) ∈ 𝑉))
39	38	simpld 500	. . . . . . . . . . . . . . 15 ⊢ (𝐹(Walks‘𝐺)𝑃 → (𝑃‘0) ∈ 𝑉)
40	6, 7, 39	3syl 19	. . . . . . . . . . . . . 14 ⊢ (𝜑 → (𝑃‘0) ∈ 𝑉)
41	40	ad2antrr 739	. . . . . . . . . . . . 13 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → (𝑃‘0) ∈ 𝑉)
42	20	wlkp 30198	. . . . . . . . . . . . . . . 16 ⊢ (𝐹(Walks‘𝐺)𝑃 → 𝑃:(0...(♯‘𝐹))⟶𝑉)
43	6, 7, 42	3syl 19	. . . . . . . . . . . . . . 15 ⊢ (𝜑 → 𝑃:(0...(♯‘𝐹))⟶𝑉)
44	43	ad2antrr 739	. . . . . . . . . . . . . 14 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → 𝑃:(0...(♯‘𝐹))⟶𝑉)
45		peano2nn0 12647	. . . . . . . . . . . . . . . . . . 19 ⊢ (𝑛 ∈ ℕ0 → (𝑛 + 1) ∈ ℕ0)
46	45	adantl 487	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝜑 ∧ 𝑛 ∈ ℕ0) → (𝑛 + 1) ∈ ℕ0)
47	46	adantr 486	. . . . . . . . . . . . . . . . 17 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → (𝑛 + 1) ∈ ℕ0)
48		nn0uz 13004	. . . . . . . . . . . . . . . . 17 ⊢ ℕ0 = (ℤ≥‘0)
49	47, 48	eleqtrdi 2870	. . . . . . . . . . . . . . . 16 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → (𝑛 + 1) ∈ (ℤ≥‘0))
50	9	ad2antrr 739	. . . . . . . . . . . . . . . . 17 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → (♯‘𝐹) ∈ ℕ0)
51	50	nn0zd 12719	. . . . . . . . . . . . . . . 16 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → (♯‘𝐹) ∈ ℤ)
52		elfz5 13649	. . . . . . . . . . . . . . . 16 ⊢ (((𝑛 + 1) ∈ (ℤ≥‘0) ∧ (♯‘𝐹) ∈ ℤ) → ((𝑛 + 1) ∈ (0...(♯‘𝐹)) ↔ (𝑛 + 1) ≤ (♯‘𝐹)))
53	49, 51, 52	syl2anc 596	. . . . . . . . . . . . . . 15 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → ((𝑛 + 1) ∈ (0...(♯‘𝐹)) ↔ (𝑛 + 1) ≤ (♯‘𝐹)))
54	31, 53	mpbird 260	. . . . . . . . . . . . . 14 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → (𝑛 + 1) ∈ (0...(♯‘𝐹)))
55	44, 54	ffvelcdmd 7085	. . . . . . . . . . . . 13 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → (𝑃‘(𝑛 + 1)) ∈ 𝑉)
56	41, 55	prssd 4782	. . . . . . . . . . . 12 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → {(𝑃‘0), (𝑃‘(𝑛 + 1))} ⊆ 𝑉)
57		prex 5395	. . . . . . . . . . . . 13 ⊢ {(𝑃‘0), (𝑃‘(𝑛 + 1))} ∈ V
58	57	elpw 4560	. . . . . . . . . . . 12 ⊢ ({(𝑃‘0), (𝑃‘(𝑛 + 1))} ∈ 𝒫 𝑉 ↔ {(𝑃‘0), (𝑃‘(𝑛 + 1))} ⊆ 𝑉)
59	56, 58	sylibr 237	. . . . . . . . . . 11 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → {(𝑃‘0), (𝑃‘(𝑛 + 1))} ∈ 𝒫 𝑉)
60		ifcl 4527	. . . . . . . . . . 11 ⊢ ((∅ ∈ 𝒫 𝑉 ∧ {(𝑃‘0), (𝑃‘(𝑛 + 1))} ∈ 𝒫 𝑉) → if((𝑃‘0) = (𝑃‘(𝑛 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑛 + 1))}) ∈ 𝒫 𝑉)
61	37, 59, 60	sylancr 599	. . . . . . . . . 10 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → if((𝑃‘0) = (𝑃‘(𝑛 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑛 + 1))}) ∈ 𝒫 𝑉)
62	61	elpwid 4565	. . . . . . . . 9 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → if((𝑃‘0) = (𝑃‘(𝑛 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑛 + 1))}) ⊆ 𝑉)
63	62	sseld 3907	. . . . . . . 8 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → (𝑦 ∈ if((𝑃‘0) = (𝑃‘(𝑛 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑛 + 1))}) → 𝑦 ∈ 𝑉))
64	63	pm4.71rd 572	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → (𝑦 ∈ if((𝑃‘0) = (𝑃‘(𝑛 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑛 + 1))}) ↔ (𝑦 ∈ 𝑉 ∧ 𝑦 ∈ if((𝑃‘0) = (𝑃‘(𝑛 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑛 + 1))}))))
65	36, 64	bitr4d 285	. . . . . 6 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → ((𝑦 ∈ 𝑉 ∧ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑦)) ↔ 𝑦 ∈ if((𝑃‘0) = (𝑃‘(𝑛 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑛 + 1))})))
66	19, 65	bitrid 286	. . . . 5 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → (𝑦 ∈ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑥)} ↔ 𝑦 ∈ if((𝑃‘0) = (𝑃‘(𝑛 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑛 + 1))})))
67	66	eqrdv 2758	. . . 4 ⊢ (((𝜑 ∧ 𝑛 ∈ ℕ0) ∧ ((𝑛 + 1) ≤ (♯‘𝐹) ∧ {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}))) → {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘(𝑛 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑛 + 1))}))
68	67	exp32 426	. . 3 ⊢ ((𝜑 ∧ 𝑛 ∈ ℕ0) → ((𝑛 + 1) ≤ (♯‘𝐹) → ({𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)}) → {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘(𝑛 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑛 + 1))}))))
69	68	a2d 30	. 2 ⊢ ((𝜑 ∧ 𝑛 ∈ ℕ0) → (((𝑛 + 1) ≤ (♯‘𝐹) → {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)})) → ((𝑛 + 1) ≤ (♯‘𝐹) → {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘(𝑛 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑛 + 1))}))))
70	15, 69	syld 48	1 ⊢ ((𝜑 ∧ 𝑛 ∈ ℕ0) → ((𝑛 ≤ (♯‘𝐹) → {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑛)))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑛), ∅, {(𝑃‘0), (𝑃‘𝑛)})) → ((𝑛 + 1) ≤ (♯‘𝐹) → {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑛 + 1))))⟩)‘𝑥)} = if((𝑃‘0) = (𝑃‘(𝑛 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑛 + 1))}))))

This proof depends on syntax axioms:  ¬ wn 3   → wi 4   ↔ wb 209   ∧ wa 401   = wceq 1569   ∈ wcel 2144  {crab 3412   ⊆ wss 3895  ∅c0 4278  ifcif 4481  𝒫 cpw 4556  {cpr 4585  ⟨cop 4589   class class class wbr 5102   ↾ cres 5652   “ cima 5653  Fun wfun 6532  ⟶wf 6534  ‘cfv 6538  (class class class)co 7420  ℝcr 11200  0cc0 11201  1c1 11202   + caddc 11204   ≤ cle 11345  2c2 12398  ℕ₀cn0 12607  ℤcz 12694  ℤ_≥cuz 12966  ...cfz 13640  ..^cfzo 13789  ♯chash 14475   ∥ cdvds 16423  Vtxcvtx 29575  iEdgciedg 29576  UPGraphcupgr 29659  VtxDegcvtxdg 30047  Walkscwlks 30178  EulerPathsceupth 30799

This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1827  ax-4 1841  ax-5 1942  ax-6 1999  ax-7 2040  ax-8 2146  ax-9 2154  ax-10 2177  ax-11 2193  ax-12 2212  ax-ext 2732  ax-rep 5231  ax-sep 5248  ax-nul 5259  ax-pow 5326  ax-pr 5390  ax-un 7751  ax-cnex 11257  ax-resscn 11258  ax-1cn 11259  ax-icn 11260  ax-addcl 11261  ax-addrcl 11262  ax-mulcl 11263  ax-mulrcl 11264  ax-mulcom 11265  ax-addass 11266  ax-mulass 11267  ax-distr 11268  ax-i2m1 11269  ax-1ne0 11270  ax-1rid 11271  ax-rnegex 11272  ax-rrecex 11273  ax-cnre 11274  ax-pre-lttri 11275  ax-pre-lttrn 11276  ax-pre-ltadd 11277  ax-pre-mulgt0 11278  ax-pre-sup 11279

This proof depends on definitions:  df-bi 210  df-an 402  df-or 862  df-ifp 1079  df-3or 1104  df-3an 1105  df-tru 1572  df-fal 1582  df-ex 1812  df-nf 1816  df-sb 2099  df-mo 2564  df-eu 2594  df-clab 2739  df-cleq 2752  df-clel 2835  df-nfc 2909  df-ne 2956  df-nel 3062  df-ral 3077  df-rex 3087  df-rmo 3365  df-reu 3366  df-rab 3413  df-v 3452  df-sbc 3739  df-csb 3847  df-ss 3896  df-pss 4014  df-dif 4047  df-in 4091  df-un 4151  df-nul 4279  df-if 4482  df-pw 4558  df-sn 4584  df-pr 4586  df-op 4590  df-uni 4867  df-int 4907  df-iun 4952  df-br 5103  df-opab 5167  df-mpt 5186  df-tr 5212  df-id 5545  df-eprel 5550  df-po 5558  df-so 5559  df-fr 5603  df-we 5605  df-xp 5656  df-rel 5657  df-cnv 5658  df-co 5659  df-dm 5660  df-rn 5661  df-res 5662  df-ima 5663  df-pred 6304  df-ord 6365  df-on 6366  df-lim 6367  df-suc 6368  df-iota 6494  df-fun 6540  df-fn 6541  df-f 6542  df-f1 6543  df-fo 6544  df-f1o 6545  df-fv 6546  df-riota 7377  df-ov 7423  df-oprab 7424  df-mpo 7425  df-om 7878  df-1st 8001  df-2nd 8002  df-frecs 8300  df-wrecs 8331  df-recs 8380  df-rdg 8419  df-1o 8477  df-2o 8478  df-oadd 8481  df-er 8718  df-map 8850  df-pm 8851  df-en 8975  df-dom 8976  df-sdom 8977  df-fin 8978  df-sup 9435  df-inf 9436  df-dju 9983  df-card 10021  df-pnf 11346  df-mnf 11347  df-xr 11348  df-ltxr 11349  df-le 11350  df-sub 11544  df-neg 11545  df-div 11975  df-nn 12337  df-2 12406  df-3 12407  df-n0 12608  df-xnn0 12681  df-z 12695  df-uz 12967  df-rp 13122  df-xadd 13243  df-fz 13641  df-fzo 13790  df-seq 14146  df-exp 14206  df-hash 14476  df-word 14660  df-cj 15267  df-re 15268  df-im 15269  df-sqrt 15403  df-abs 15404  df-dvds 16424  df-vtx 29577  df-iedg 29578  df-edg 29627  df-uhgr 29637  df-ushgr 29638  df-upgr 29661  df-uspgr 29732  df-vtxdg 30048  df-wlks 30181  df-trls 30276  df-eupth 30800

This theorem is used by:  eupth2  30841