cycl3grtri - Mathbox for Alexander van der Vekens

	Mathbox for Alexander van der Vekens		< Previous Next > Nearby theorems
Mirrors > Home > MPE Home > Th. List > Mathboxes > cycl3grtri		Structured version Visualization version GIF version

Theorem cycl3grtri 48560

Description: The vertices of a cycle of size 3 are a triangle in a graph. (Contributed by AV, 5-Oct-2025.)

**Hypotheses**
Ref	Expression
cycl3grtri.g	⊢ (𝜑 → 𝐺 ∈ UPGraph)
cycl3grtri.c	⊢ (𝜑 → 𝐹(Cycles‘𝐺)𝑃)
cycl3grtri.n	⊢ (𝜑 → (♯‘𝐹) = 3)

**Assertion**
Ref	Expression
cycl3grtri	⊢ (𝜑 → ran 𝑃 ∈ (GrTriangles‘𝐺))

Proof of Theorem cycl3grtri Dummy variables 𝑥 𝑦 𝑧 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		cycl3grtri.n	. 2 ⊢ (𝜑 → (♯‘𝐹) = 3)
2		cycl3grtri.c	. 2 ⊢ (𝜑 → 𝐹(Cycles‘𝐺)𝑃)
3		cyclprop 30000	. . . 4 ⊢ (𝐹(Cycles‘𝐺)𝑃 → (𝐹(Paths‘𝐺)𝑃 ∧ (𝑃‘0) = (𝑃‘(♯‘𝐹))))
4		tpeq1 4702	. . . . . . . . . . . . 13 ⊢ (𝑥 = (𝑃‘0) → {𝑥, 𝑦, 𝑧} = {(𝑃‘0), 𝑦, 𝑧})
5	4	eqeq2d 2774	. . . . . . . . . . . 12 ⊢ (𝑥 = (𝑃‘0) → (ran 𝑃 = {𝑥, 𝑦, 𝑧} ↔ ran 𝑃 = {(𝑃‘0), 𝑦, 𝑧}))
6		preq1 4693	. . . . . . . . . . . . . 14 ⊢ (𝑥 = (𝑃‘0) → {𝑥, 𝑦} = {(𝑃‘0), 𝑦})
7	6	eleq1d 2848	. . . . . . . . . . . . 13 ⊢ (𝑥 = (𝑃‘0) → ({𝑥, 𝑦} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), 𝑦} ∈ (Edg‘𝐺)))
8		preq1 4693	. . . . . . . . . . . . . 14 ⊢ (𝑥 = (𝑃‘0) → {𝑥, 𝑧} = {(𝑃‘0), 𝑧})
9	8	eleq1d 2848	. . . . . . . . . . . . 13 ⊢ (𝑥 = (𝑃‘0) → ({𝑥, 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺)))
10	7, 9	3anbi12d 1459	. . . . . . . . . . . 12 ⊢ (𝑥 = (𝑃‘0) → (({𝑥, 𝑦} ∈ (Edg‘𝐺) ∧ {𝑥, 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺)) ↔ ({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺))))
11	5, 10	3anbi13d 1460	. . . . . . . . . . 11 ⊢ (𝑥 = (𝑃‘0) → ((ran 𝑃 = {𝑥, 𝑦, 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({𝑥, 𝑦} ∈ (Edg‘𝐺) ∧ {𝑥, 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺))) ↔ (ran 𝑃 = {(𝑃‘0), 𝑦, 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺)))))
12		tpeq2 4703	. . . . . . . . . . . . 13 ⊢ (𝑦 = (𝑃‘1) → {(𝑃‘0), 𝑦, 𝑧} = {(𝑃‘0), (𝑃‘1), 𝑧})
13	12	eqeq2d 2774	. . . . . . . . . . . 12 ⊢ (𝑦 = (𝑃‘1) → (ran 𝑃 = {(𝑃‘0), 𝑦, 𝑧} ↔ ran 𝑃 = {(𝑃‘0), (𝑃‘1), 𝑧}))
14		preq2 4694	. . . . . . . . . . . . . 14 ⊢ (𝑦 = (𝑃‘1) → {(𝑃‘0), 𝑦} = {(𝑃‘0), (𝑃‘1)})
15	14	eleq1d 2848	. . . . . . . . . . . . 13 ⊢ (𝑦 = (𝑃‘1) → ({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺)))
16		preq1 4693	. . . . . . . . . . . . . 14 ⊢ (𝑦 = (𝑃‘1) → {𝑦, 𝑧} = {(𝑃‘1), 𝑧})
17	16	eleq1d 2848	. . . . . . . . . . . . 13 ⊢ (𝑦 = (𝑃‘1) → ({𝑦, 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘1), 𝑧} ∈ (Edg‘𝐺)))
18	15, 17	3anbi13d 1460	. . . . . . . . . . . 12 ⊢ (𝑦 = (𝑃‘1) → (({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺)) ↔ ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), 𝑧} ∈ (Edg‘𝐺))))
19	13, 18	3anbi13d 1460	. . . . . . . . . . 11 ⊢ (𝑦 = (𝑃‘1) → ((ran 𝑃 = {(𝑃‘0), 𝑦, 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺))) ↔ (ran 𝑃 = {(𝑃‘0), (𝑃‘1), 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), 𝑧} ∈ (Edg‘𝐺)))))
20		tpeq3 4704	. . . . . . . . . . . . 13 ⊢ (𝑧 = (𝑃‘2) → {(𝑃‘0), (𝑃‘1), 𝑧} = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
21	20	eqeq2d 2774	. . . . . . . . . . . 12 ⊢ (𝑧 = (𝑃‘2) → (ran 𝑃 = {(𝑃‘0), (𝑃‘1), 𝑧} ↔ ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)}))
22		preq2 4694	. . . . . . . . . . . . . 14 ⊢ (𝑧 = (𝑃‘2) → {(𝑃‘0), 𝑧} = {(𝑃‘0), (𝑃‘2)})
23	22	eleq1d 2848	. . . . . . . . . . . . 13 ⊢ (𝑧 = (𝑃‘2) → ({(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺)))
24		preq2 4694	. . . . . . . . . . . . . 14 ⊢ (𝑧 = (𝑃‘2) → {(𝑃‘1), 𝑧} = {(𝑃‘1), (𝑃‘2)})
25	24	eleq1d 2848	. . . . . . . . . . . . 13 ⊢ (𝑧 = (𝑃‘2) → ({(𝑃‘1), 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺)))
26	23, 25	3anbi23d 1461	. . . . . . . . . . . 12 ⊢ (𝑧 = (𝑃‘2) → (({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), 𝑧} ∈ (Edg‘𝐺)) ↔ ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺))))
27	21, 26	3anbi13d 1460	. . . . . . . . . . 11 ⊢ (𝑧 = (𝑃‘2) → ((ran 𝑃 = {(𝑃‘0), (𝑃‘1), 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), 𝑧} ∈ (Edg‘𝐺))) ↔ (ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∧ (♯‘ran 𝑃) = 3 ∧ ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺)))))
28		pthiswlk 29932	. . . . . . . . . . . . . 14 ⊢ (𝐹(Paths‘𝐺)𝑃 → 𝐹(Walks‘𝐺)𝑃)
29		eqid 2763	. . . . . . . . . . . . . . 15 ⊢ (Vtx‘𝐺) = (Vtx‘𝐺)
30	29	wlkp 29824	. . . . . . . . . . . . . 14 ⊢ (𝐹(Walks‘𝐺)𝑃 → 𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺))
31		simpl 486	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺))
32		3nn0 12509	. . . . . . . . . . . . . . . . . . 19 ⊢ 3 ∈ ℕ₀
33		0elfz 13639	. . . . . . . . . . . . . . . . . . 19 ⊢ (3 ∈ ℕ₀ → 0 ∈ (0...3))
34	32, 33	ax-mp 5	. . . . . . . . . . . . . . . . . 18 ⊢ 0 ∈ (0...3)
35		oveq2 7404	. . . . . . . . . . . . . . . . . 18 ⊢ ((♯‘𝐹) = 3 → (0...(♯‘𝐹)) = (0...3))
36	34, 35	eleqtrrid 2870	. . . . . . . . . . . . . . . . 17 ⊢ ((♯‘𝐹) = 3 → 0 ∈ (0...(♯‘𝐹)))
37	36	ad2antll 739	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 0 ∈ (0...(♯‘𝐹)))
38	31, 37	ffvelcdmd 7066	. . . . . . . . . . . . . . 15 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘0) ∈ (Vtx‘𝐺))
39	38	ex 416	. . . . . . . . . . . . . 14 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘0) ∈ (Vtx‘𝐺)))
40	28, 30, 39	3syl 18	. . . . . . . . . . . . 13 ⊢ (𝐹(Paths‘𝐺)𝑃 → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘0) ∈ (Vtx‘𝐺)))
41	40	adantl 485	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘0) ∈ (Vtx‘𝐺)))
42	41	imp 410	. . . . . . . . . . 11 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘0) ∈ (Vtx‘𝐺))
43		1nn0 12507	. . . . . . . . . . . . . . . . . . 19 ⊢ 1 ∈ ℕ₀
44		1le3 12442	. . . . . . . . . . . . . . . . . . 19 ⊢ 1 ≤ 3
45		elfz2nn0 13633	. . . . . . . . . . . . . . . . . . 19 ⊢ (1 ∈ (0...3) ↔ (1 ∈ ℕ₀ ∧ 3 ∈ ℕ₀ ∧ 1 ≤ 3))
46	43, 32, 44, 45	mpbir3an 1356	. . . . . . . . . . . . . . . . . 18 ⊢ 1 ∈ (0...3)
47	46, 35	eleqtrrid 2870	. . . . . . . . . . . . . . . . 17 ⊢ ((♯‘𝐹) = 3 → 1 ∈ (0...(♯‘𝐹)))
48	47	ad2antll 739	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 1 ∈ (0...(♯‘𝐹)))
49	31, 48	ffvelcdmd 7066	. . . . . . . . . . . . . . 15 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘1) ∈ (Vtx‘𝐺))
50	49	ex 416	. . . . . . . . . . . . . 14 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘1) ∈ (Vtx‘𝐺)))
51	28, 30, 50	3syl 18	. . . . . . . . . . . . 13 ⊢ (𝐹(Paths‘𝐺)𝑃 → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘1) ∈ (Vtx‘𝐺)))
52	51	adantl 485	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘1) ∈ (Vtx‘𝐺)))
53	52	imp 410	. . . . . . . . . . 11 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘1) ∈ (Vtx‘𝐺))
54		2nn0 12508	. . . . . . . . . . . . . . . . . . 19 ⊢ 2 ∈ ℕ₀
55		2re 12302	. . . . . . . . . . . . . . . . . . . 20 ⊢ 2 ∈ ℝ
56		3re 12308	. . . . . . . . . . . . . . . . . . . 20 ⊢ 3 ∈ ℝ
57		2lt3 12401	. . . . . . . . . . . . . . . . . . . 20 ⊢ 2 < 3
58	55, 56, 57	ltleii 11317	. . . . . . . . . . . . . . . . . . 19 ⊢ 2 ≤ 3
59		elfz2nn0 13633	. . . . . . . . . . . . . . . . . . 19 ⊢ (2 ∈ (0...3) ↔ (2 ∈ ℕ₀ ∧ 3 ∈ ℕ₀ ∧ 2 ≤ 3))
60	54, 32, 58, 59	mpbir3an 1356	. . . . . . . . . . . . . . . . . 18 ⊢ 2 ∈ (0...3)
61	60, 35	eleqtrrid 2870	. . . . . . . . . . . . . . . . 17 ⊢ ((♯‘𝐹) = 3 → 2 ∈ (0...(♯‘𝐹)))
62	61	ad2antll 739	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 2 ∈ (0...(♯‘𝐹)))
63	31, 62	ffvelcdmd 7066	. . . . . . . . . . . . . . 15 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘2) ∈ (Vtx‘𝐺))
64	63	ex 416	. . . . . . . . . . . . . 14 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘2) ∈ (Vtx‘𝐺)))
65	28, 30, 64	3syl 18	. . . . . . . . . . . . 13 ⊢ (𝐹(Paths‘𝐺)𝑃 → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘2) ∈ (Vtx‘𝐺)))
66	65	adantl 485	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘2) ∈ (Vtx‘𝐺)))
67	66	imp 410	. . . . . . . . . . 11 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘2) ∈ (Vtx‘𝐺))
68		fdm 6701	. . . . . . . . . . . . . . . . . . . 20 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → dom 𝑃 = (0...(♯‘𝐹)))
69		elnn0uz 12890	. . . . . . . . . . . . . . . . . . . . . . . . 25 ⊢ (3 ∈ ℕ₀ ↔ 3 ∈ (ℤ_≥‘0))
70	32, 69	mpbi 232	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ 3 ∈ (ℤ_≥‘0)
71		fzisfzounsn 13796	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (3 ∈ (ℤ_≥‘0) → (0...3) = ((0..^3) ∪ {3}))
72	70, 71	ax-mp 5	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (0...3) = ((0..^3) ∪ {3})
73		fzo0to3tp 13768	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (0..^3) = {0, 1, 2}
74	73	uneq1i 4118	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((0..^3) ∪ {3}) = ({0, 1, 2} ∪ {3})
75	72, 74	eqtri 2786	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ (0...3) = ({0, 1, 2} ∪ {3})
76	35, 75	eqtrdi 2814	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((♯‘𝐹) = 3 → (0...(♯‘𝐹)) = ({0, 1, 2} ∪ {3}))
77	76	adantl 485	. . . . . . . . . . . . . . . . . . . 20 ⊢ (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (0...(♯‘𝐹)) = ({0, 1, 2} ∪ {3}))
78	68, 77	sylan9eq 2818	. . . . . . . . . . . . . . . . . . 19 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → dom 𝑃 = ({0, 1, 2} ∪ {3}))
79	78	imaeq2d 6049	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃 “ dom 𝑃) = (𝑃 “ ({0, 1, 2} ∪ {3})))
80		imadmrn 6059	. . . . . . . . . . . . . . . . . 18 ⊢ (𝑃 “ dom 𝑃) = ran 𝑃
81		imaundi 6134	. . . . . . . . . . . . . . . . . 18 ⊢ (𝑃 “ ({0, 1, 2} ∪ {3})) = ((𝑃 “ {0, 1, 2}) ∪ (𝑃 “ {3}))
82	79, 80, 81	3eqtr3g 2821	. . . . . . . . . . . . . . . . 17 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ran 𝑃 = ((𝑃 “ {0, 1, 2}) ∪ (𝑃 “ {3})))
83		ffn 6691	. . . . . . . . . . . . . . . . . . . 20 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → 𝑃 Fn (0...(♯‘𝐹)))
84	83	adantr 484	. . . . . . . . . . . . . . . . . . 19 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 𝑃 Fn (0...(♯‘𝐹)))
85	84, 37, 48, 62	fnimatpd 6951	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃 “ {0, 1, 2}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
86		nn0fz0 13640	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (3 ∈ ℕ₀ ↔ 3 ∈ (0...3))
87	32, 86	mpbi 232	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ 3 ∈ (0...3)
88	87, 35	eleqtrrid 2870	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((♯‘𝐹) = 3 → 3 ∈ (0...(♯‘𝐹)))
89	88	adantl 485	. . . . . . . . . . . . . . . . . . . 20 ⊢ (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → 3 ∈ (0...(♯‘𝐹)))
90		fnsnfv 6946	. . . . . . . . . . . . . . . . . . . 20 ⊢ ((𝑃 Fn (0...(♯‘𝐹)) ∧ 3 ∈ (0...(♯‘𝐹))) → {(𝑃‘3)} = (𝑃 “ {3}))
91	83, 89, 90	syl2an 605	. . . . . . . . . . . . . . . . . . 19 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → {(𝑃‘3)} = (𝑃 “ {3}))
92	91	eqcomd 2769	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃 “ {3}) = {(𝑃‘3)})
93	85, 92	uneq12d 4123	. . . . . . . . . . . . . . . . 17 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ((𝑃 “ {0, 1, 2}) ∪ (𝑃 “ {3})) = ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}))
94		fveq2 6867	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((♯‘𝐹) = 3 → (𝑃‘(♯‘𝐹)) = (𝑃‘3))
95	94	eqeq2d 2774	. . . . . . . . . . . . . . . . . . . 20 ⊢ ((♯‘𝐹) = 3 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ↔ (𝑃‘0) = (𝑃‘3)))
96		sneq 4593	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((𝑃‘3) = (𝑃‘0) → {(𝑃‘3)} = {(𝑃‘0)})
97	96	eqcoms 2771	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝑃‘0) = (𝑃‘3) → {(𝑃‘3)} = {(𝑃‘0)})
98	97	uneq2d 4122	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((𝑃‘0) = (𝑃‘3) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}) = ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘0)}))
99		snsstp1 4775	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ {(𝑃‘0)} ⊆ {(𝑃‘0), (𝑃‘1), (𝑃‘2)}
100	99	a1i 11	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝑃‘0) = (𝑃‘3) → {(𝑃‘0)} ⊆ {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
101		ssequn2 4142	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ({(𝑃‘0)} ⊆ {(𝑃‘0), (𝑃‘1), (𝑃‘2)} ↔ ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘0)}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
102	100, 101	sylib 220	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((𝑃‘0) = (𝑃‘3) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘0)}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
103	98, 102	eqtrd 2798	. . . . . . . . . . . . . . . . . . . 20 ⊢ ((𝑃‘0) = (𝑃‘3) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
104	95, 103	biimtrdi 255	. . . . . . . . . . . . . . . . . . 19 ⊢ ((♯‘𝐹) = 3 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)}))
105	104	impcom 411	. . . . . . . . . . . . . . . . . 18 ⊢ (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
106	105	adantl 485	. . . . . . . . . . . . . . . . 17 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
107	82, 93, 106	3eqtrd 2802	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
108	107	ex 416	. . . . . . . . . . . . . . 15 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)}))
109	28, 30, 108	3syl 18	. . . . . . . . . . . . . 14 ⊢ (𝐹(Paths‘𝐺)𝑃 → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)}))
110	109	adantl 485	. . . . . . . . . . . . 13 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)}))
111	110	imp 410	. . . . . . . . . . . 12 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
112		breq2 5105	. . . . . . . . . . . . . . . 16 ⊢ ((♯‘𝐹) = 3 → (1 ≤ (♯‘𝐹) ↔ 1 ≤ 3))
113	44, 112	mpbiri 260	. . . . . . . . . . . . . . 15 ⊢ ((♯‘𝐹) = 3 → 1 ≤ (♯‘𝐹))
114	113	ad2antll 739	. . . . . . . . . . . . . 14 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 1 ≤ (♯‘𝐹))
115	2	ad2antrr 736	. . . . . . . . . . . . . 14 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 𝐹(Cycles‘𝐺)𝑃)
116		cyclnumvtx 30007	. . . . . . . . . . . . . 14 ⊢ ((1 ≤ (♯‘𝐹) ∧ 𝐹(Cycles‘𝐺)𝑃) → (♯‘ran 𝑃) = (♯‘𝐹))
117	114, 115, 116	syl2anc 593	. . . . . . . . . . . . 13 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (♯‘ran 𝑃) = (♯‘𝐹))
118	1	ad2antrr 736	. . . . . . . . . . . . 13 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (♯‘𝐹) = 3)
119	117, 118	eqtrd 2798	. . . . . . . . . . . 12 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (♯‘ran 𝑃) = 3)
120		cycl3grtri.g	. . . . . . . . . . . . 13 ⊢ (𝜑 → 𝐺 ∈ UPGraph)
121		cycl3grtrilem 48559	. . . . . . . . . . . . 13 ⊢ (((𝐺 ∈ UPGraph ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺)))
122	120, 121	sylanl1 690	. . . . . . . . . . . 12 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺)))
123	111, 119, 122	3jca 1142	. . . . . . . . . . 11 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∧ (♯‘ran 𝑃) = 3 ∧ ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺))))
124	11, 19, 27, 42, 53, 67, 123	3rspcedvdw 3600	. . . . . . . . . 10 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ∃𝑥 ∈ (Vtx‘𝐺)∃𝑦 ∈ (Vtx‘𝐺)∃𝑧 ∈ (Vtx‘𝐺)(ran 𝑃 = {𝑥, 𝑦, 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({𝑥, 𝑦} ∈ (Edg‘𝐺) ∧ {𝑥, 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺))))
125		eqid 2763	. . . . . . . . . . 11 ⊢ (Edg‘𝐺) = (Edg‘𝐺)
126	29, 125	isgrtri 48556	. . . . . . . . . 10 ⊢ (ran 𝑃 ∈ (GrTriangles‘𝐺) ↔ ∃𝑥 ∈ (Vtx‘𝐺)∃𝑦 ∈ (Vtx‘𝐺)∃𝑧 ∈ (Vtx‘𝐺)(ran 𝑃 = {𝑥, 𝑦, 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({𝑥, 𝑦} ∈ (Edg‘𝐺) ∧ {𝑥, 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺))))
127	124, 126	sylibr 236	. . . . . . . . 9 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ran 𝑃 ∈ (GrTriangles‘𝐺))
128	127	exp32 424	. . . . . . . 8 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) → ((♯‘𝐹) = 3 → ran 𝑃 ∈ (GrTriangles‘𝐺))))
129	128	com23 86	. . . . . . 7 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → ((♯‘𝐹) = 3 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) → ran 𝑃 ∈ (GrTriangles‘𝐺))))
130	129	expcom 417	. . . . . 6 ⊢ (𝐹(Paths‘𝐺)𝑃 → (𝜑 → ((♯‘𝐹) = 3 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) → ran 𝑃 ∈ (GrTriangles‘𝐺)))))
131	130	com24 95	. . . . 5 ⊢ (𝐹(Paths‘𝐺)𝑃 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) → ((♯‘𝐹) = 3 → (𝜑 → ran 𝑃 ∈ (GrTriangles‘𝐺)))))
132	131	imp 410	. . . 4 ⊢ ((𝐹(Paths‘𝐺)𝑃 ∧ (𝑃‘0) = (𝑃‘(♯‘𝐹))) → ((♯‘𝐹) = 3 → (𝜑 → ran 𝑃 ∈ (GrTriangles‘𝐺))))
133	3, 132	syl 17	. . 3 ⊢ (𝐹(Cycles‘𝐺)𝑃 → ((♯‘𝐹) = 3 → (𝜑 → ran 𝑃 ∈ (GrTriangles‘𝐺))))
134	133	com13 88	. 2 ⊢ (𝜑 → ((♯‘𝐹) = 3 → (𝐹(Cycles‘𝐺)𝑃 → ran 𝑃 ∈ (GrTriangles‘𝐺))))
135	1, 2, 134	mp2d 49	1 ⊢ (𝜑 → ran 𝑃 ∈ (GrTriangles‘𝐺))

Colors of variables: wff setvar class

Syntax hints: → wi 4 ∧ wa 399 ∧ w3a 1099 = wceq 1561 ∈ wcel 2143 ∃wrex 3087 ∪ cun 3903 ⊆ wss 3905 {csn 4583 {cpr 4585 {ctp 4587 class class class wbr 5101 dom cdm 5648 ran crn 5649 “ cima 5651 Fn wfn 6516 ⟶wf 6517 ‘cfv 6521 (class class class)co 7396 0cc0 11084 1c1 11085 ≤ cle 11228 2c2 12282 3c3 12283 ℕ₀cn0 12491 ℤ_≥cuz 12849 ...cfz 13522 ..^cfzo 13669 ♯chash 14353 Vtxcvtx 29204 Edgcedg 29255 UPGraphcupgr 29288 Walkscwlks 29804 Pathscpths 29917 Cyclesccycls 29992 GrTrianglescgrtri 48550

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1816 ax-4 1830 ax-5 1931 ax-6 1988 ax-7 2029 ax-8 2145 ax-9 2153 ax-10 2176 ax-11 2192 ax-12 2213 ax-ext 2735 ax-rep 5228 ax-sep 5247 ax-nul 5257 ax-pow 5323 ax-pr 5391 ax-un 7718 ax-cnex 11140 ax-resscn 11141 ax-1cn 11142 ax-icn 11143 ax-addcl 11144 ax-addrcl 11145 ax-mulcl 11146 ax-mulrcl 11147 ax-mulcom 11148 ax-addass 11149 ax-mulass 11150 ax-distr 11151 ax-i2m1 11152 ax-1ne0 11153 ax-1rid 11154 ax-rnegex 11155 ax-rrecex 11156 ax-cnre 11157 ax-pre-lttri 11158 ax-pre-lttrn 11159 ax-pre-ltadd 11160 ax-pre-mulgt0 11161

This theorem depends on definitions: df-bi 209 df-an 400 df-or 859 df-ifp 1075 df-3or 1100 df-3an 1101 df-tru 1564 df-fal 1574 df-ex 1801 df-nf 1805 df-sb 2092 df-mo 2567 df-eu 2597 df-clab 2742 df-cleq 2755 df-clel 2838 df-nfc 2912 df-ne 2959 df-nel 3063 df-ral 3078 df-rex 3088 df-reu 3369 df-rab 3416 df-v 3457 df-sbc 3746 df-csb 3854 df-dif 3908 df-un 3910 df-in 3912 df-ss 3922 df-pss 3925 df-nul 4287 df-if 4482 df-pw 4558 df-sn 4584 df-pr 4586 df-tp 4588 df-op 4590 df-uni 4867 df-int 4907 df-iun 4952 df-br 5102 df-opab 5164 df-mpt 5183 df-tr 5209 df-id 5543 df-eprel 5548 df-po 5556 df-so 5557 df-fr 5601 df-we 5603 df-xp 5654 df-rel 5655 df-cnv 5656 df-co 5657 df-dm 5658 df-rn 5659 df-res 5660 df-ima 5661 df-pred 6288 df-ord 6349 df-on 6350 df-lim 6351 df-suc 6352 df-iota 6477 df-fun 6523 df-fn 6524 df-f 6525 df-f1 6526 df-fo 6527 df-f1o 6528 df-fv 6529 df-riota 7353 df-ov 7399 df-oprab 7400 df-mpo 7401 df-om 7847 df-1st 7970 df-2nd 7971 df-frecs 8262 df-wrecs 8293 df-recs 8342 df-rdg 8381 df-1o 8437 df-2o 8438 df-3o 8439 df-oadd 8441 df-er 8678 df-map 8810 df-pm 8811 df-en 8928 df-dom 8929 df-sdom 8930 df-fin 8931 df-dju 9871 df-card 9909 df-pnf 11229 df-mnf 11230 df-xr 11231 df-ltxr 11232 df-le 11233 df-sub 11427 df-neg 11428 df-nn 12221 df-2 12290 df-3 12291 df-n0 12492 df-xnn0 12565 df-z 12579 df-uz 12850 df-fz 13523 df-fzo 13670 df-hash 14354 df-word 14537 df-edg 29256 df-uhgr 29266 df-upgr 29290 df-wlks 29807 df-trls 29898 df-pths 29921 df-cycls 29994 df-grtri 48551

This theorem is referenced by: (None)

W3C validator