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 48052

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 29778	. . . 4 ⊢ (𝐹(Cycles‘𝐺)𝑃 → (𝐹(Paths‘𝐺)𝑃 ∧ (𝑃‘0) = (𝑃‘(♯‘𝐹))))
4		tpeq1 4694	. . . . . . . . . . . . 13 ⊢ (𝑥 = (𝑃‘0) → {𝑥, 𝑦, 𝑧} = {(𝑃‘0), 𝑦, 𝑧})
5	4	eqeq2d 2742	. . . . . . . . . . . 12 ⊢ (𝑥 = (𝑃‘0) → (ran 𝑃 = {𝑥, 𝑦, 𝑧} ↔ ran 𝑃 = {(𝑃‘0), 𝑦, 𝑧}))
6		preq1 4685	. . . . . . . . . . . . . 14 ⊢ (𝑥 = (𝑃‘0) → {𝑥, 𝑦} = {(𝑃‘0), 𝑦})
7	6	eleq1d 2816	. . . . . . . . . . . . 13 ⊢ (𝑥 = (𝑃‘0) → ({𝑥, 𝑦} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), 𝑦} ∈ (Edg‘𝐺)))
8		preq1 4685	. . . . . . . . . . . . . 14 ⊢ (𝑥 = (𝑃‘0) → {𝑥, 𝑧} = {(𝑃‘0), 𝑧})
9	8	eleq1d 2816	. . . . . . . . . . . . 13 ⊢ (𝑥 = (𝑃‘0) → ({𝑥, 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺)))
10	7, 9	3anbi12d 1439	. . . . . . . . . . . 12 ⊢ (𝑥 = (𝑃‘0) → (({𝑥, 𝑦} ∈ (Edg‘𝐺) ∧ {𝑥, 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺)) ↔ ({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺))))
11	5, 10	3anbi13d 1440	. . . . . . . . . . 11 ⊢ (𝑥 = (𝑃‘0) → ((ran 𝑃 = {𝑥, 𝑦, 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({𝑥, 𝑦} ∈ (Edg‘𝐺) ∧ {𝑥, 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺))) ↔ (ran 𝑃 = {(𝑃‘0), 𝑦, 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺)))))
12		tpeq2 4695	. . . . . . . . . . . . 13 ⊢ (𝑦 = (𝑃‘1) → {(𝑃‘0), 𝑦, 𝑧} = {(𝑃‘0), (𝑃‘1), 𝑧})
13	12	eqeq2d 2742	. . . . . . . . . . . 12 ⊢ (𝑦 = (𝑃‘1) → (ran 𝑃 = {(𝑃‘0), 𝑦, 𝑧} ↔ ran 𝑃 = {(𝑃‘0), (𝑃‘1), 𝑧}))
14		preq2 4686	. . . . . . . . . . . . . 14 ⊢ (𝑦 = (𝑃‘1) → {(𝑃‘0), 𝑦} = {(𝑃‘0), (𝑃‘1)})
15	14	eleq1d 2816	. . . . . . . . . . . . 13 ⊢ (𝑦 = (𝑃‘1) → ({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺)))
16		preq1 4685	. . . . . . . . . . . . . 14 ⊢ (𝑦 = (𝑃‘1) → {𝑦, 𝑧} = {(𝑃‘1), 𝑧})
17	16	eleq1d 2816	. . . . . . . . . . . . 13 ⊢ (𝑦 = (𝑃‘1) → ({𝑦, 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘1), 𝑧} ∈ (Edg‘𝐺)))
18	15, 17	3anbi13d 1440	. . . . . . . . . . . 12 ⊢ (𝑦 = (𝑃‘1) → (({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺)) ↔ ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), 𝑧} ∈ (Edg‘𝐺))))
19	13, 18	3anbi13d 1440	. . . . . . . . . . 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 4696	. . . . . . . . . . . . 13 ⊢ (𝑧 = (𝑃‘2) → {(𝑃‘0), (𝑃‘1), 𝑧} = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
21	20	eqeq2d 2742	. . . . . . . . . . . 12 ⊢ (𝑧 = (𝑃‘2) → (ran 𝑃 = {(𝑃‘0), (𝑃‘1), 𝑧} ↔ ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)}))
22		preq2 4686	. . . . . . . . . . . . . 14 ⊢ (𝑧 = (𝑃‘2) → {(𝑃‘0), 𝑧} = {(𝑃‘0), (𝑃‘2)})
23	22	eleq1d 2816	. . . . . . . . . . . . 13 ⊢ (𝑧 = (𝑃‘2) → ({(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺)))
24		preq2 4686	. . . . . . . . . . . . . 14 ⊢ (𝑧 = (𝑃‘2) → {(𝑃‘1), 𝑧} = {(𝑃‘1), (𝑃‘2)})
25	24	eleq1d 2816	. . . . . . . . . . . . 13 ⊢ (𝑧 = (𝑃‘2) → ({(𝑃‘1), 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺)))
26	23, 25	3anbi23d 1441	. . . . . . . . . . . 12 ⊢ (𝑧 = (𝑃‘2) → (({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), 𝑧} ∈ (Edg‘𝐺)) ↔ ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺))))
27	21, 26	3anbi13d 1440	. . . . . . . . . . 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 29710	. . . . . . . . . . . . . 14 ⊢ (𝐹(Paths‘𝐺)𝑃 → 𝐹(Walks‘𝐺)𝑃)
29		eqid 2731	. . . . . . . . . . . . . . 15 ⊢ (Vtx‘𝐺) = (Vtx‘𝐺)
30	29	wlkp 29602	. . . . . . . . . . . . . 14 ⊢ (𝐹(Walks‘𝐺)𝑃 → 𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺))
31		simpl 482	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺))
32		3nn0 12405	. . . . . . . . . . . . . . . . . . 19 ⊢ 3 ∈ ℕ₀
33		0elfz 13530	. . . . . . . . . . . . . . . . . . 19 ⊢ (3 ∈ ℕ₀ → 0 ∈ (0...3))
34	32, 33	ax-mp 5	. . . . . . . . . . . . . . . . . 18 ⊢ 0 ∈ (0...3)
35		oveq2 7360	. . . . . . . . . . . . . . . . . 18 ⊢ ((♯‘𝐹) = 3 → (0...(♯‘𝐹)) = (0...3))
36	34, 35	eleqtrrid 2838	. . . . . . . . . . . . . . . . 17 ⊢ ((♯‘𝐹) = 3 → 0 ∈ (0...(♯‘𝐹)))
37	36	ad2antll 729	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 0 ∈ (0...(♯‘𝐹)))
38	31, 37	ffvelcdmd 7024	. . . . . . . . . . . . . . 15 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘0) ∈ (Vtx‘𝐺))
39	38	ex 412	. . . . . . . . . . . . . 14 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘0) ∈ (Vtx‘𝐺)))
40	28, 30, 39	3syl 18	. . . . . . . . . . . . 13 ⊢ (𝐹(Paths‘𝐺)𝑃 → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘0) ∈ (Vtx‘𝐺)))
41	40	adantl 481	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘0) ∈ (Vtx‘𝐺)))
42	41	imp 406	. . . . . . . . . . 11 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘0) ∈ (Vtx‘𝐺))
43		1nn0 12403	. . . . . . . . . . . . . . . . . . 19 ⊢ 1 ∈ ℕ₀
44		1le3 12338	. . . . . . . . . . . . . . . . . . 19 ⊢ 1 ≤ 3
45		elfz2nn0 13524	. . . . . . . . . . . . . . . . . . 19 ⊢ (1 ∈ (0...3) ↔ (1 ∈ ℕ₀ ∧ 3 ∈ ℕ₀ ∧ 1 ≤ 3))
46	43, 32, 44, 45	mpbir3an 1342	. . . . . . . . . . . . . . . . . 18 ⊢ 1 ∈ (0...3)
47	46, 35	eleqtrrid 2838	. . . . . . . . . . . . . . . . 17 ⊢ ((♯‘𝐹) = 3 → 1 ∈ (0...(♯‘𝐹)))
48	47	ad2antll 729	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 1 ∈ (0...(♯‘𝐹)))
49	31, 48	ffvelcdmd 7024	. . . . . . . . . . . . . . 15 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘1) ∈ (Vtx‘𝐺))
50	49	ex 412	. . . . . . . . . . . . . 14 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘1) ∈ (Vtx‘𝐺)))
51	28, 30, 50	3syl 18	. . . . . . . . . . . . 13 ⊢ (𝐹(Paths‘𝐺)𝑃 → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘1) ∈ (Vtx‘𝐺)))
52	51	adantl 481	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘1) ∈ (Vtx‘𝐺)))
53	52	imp 406	. . . . . . . . . . 11 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘1) ∈ (Vtx‘𝐺))
54		2nn0 12404	. . . . . . . . . . . . . . . . . . 19 ⊢ 2 ∈ ℕ₀
55		2re 12205	. . . . . . . . . . . . . . . . . . . 20 ⊢ 2 ∈ ℝ
56		3re 12211	. . . . . . . . . . . . . . . . . . . 20 ⊢ 3 ∈ ℝ
57		2lt3 12298	. . . . . . . . . . . . . . . . . . . 20 ⊢ 2 < 3
58	55, 56, 57	ltleii 11242	. . . . . . . . . . . . . . . . . . 19 ⊢ 2 ≤ 3
59		elfz2nn0 13524	. . . . . . . . . . . . . . . . . . 19 ⊢ (2 ∈ (0...3) ↔ (2 ∈ ℕ₀ ∧ 3 ∈ ℕ₀ ∧ 2 ≤ 3))
60	54, 32, 58, 59	mpbir3an 1342	. . . . . . . . . . . . . . . . . 18 ⊢ 2 ∈ (0...3)
61	60, 35	eleqtrrid 2838	. . . . . . . . . . . . . . . . 17 ⊢ ((♯‘𝐹) = 3 → 2 ∈ (0...(♯‘𝐹)))
62	61	ad2antll 729	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 2 ∈ (0...(♯‘𝐹)))
63	31, 62	ffvelcdmd 7024	. . . . . . . . . . . . . . 15 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘2) ∈ (Vtx‘𝐺))
64	63	ex 412	. . . . . . . . . . . . . 14 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘2) ∈ (Vtx‘𝐺)))
65	28, 30, 64	3syl 18	. . . . . . . . . . . . 13 ⊢ (𝐹(Paths‘𝐺)𝑃 → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘2) ∈ (Vtx‘𝐺)))
66	65	adantl 481	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘2) ∈ (Vtx‘𝐺)))
67	66	imp 406	. . . . . . . . . . 11 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘2) ∈ (Vtx‘𝐺))
68		fdm 6666	. . . . . . . . . . . . . . . . . . . 20 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → dom 𝑃 = (0...(♯‘𝐹)))
69		elnn0uz 12783	. . . . . . . . . . . . . . . . . . . . . . . . 25 ⊢ (3 ∈ ℕ₀ ↔ 3 ∈ (ℤ_≥‘0))
70	32, 69	mpbi 230	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ 3 ∈ (ℤ_≥‘0)
71		fzisfzounsn 13686	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (3 ∈ (ℤ_≥‘0) → (0...3) = ((0..^3) ∪ {3}))
72	70, 71	ax-mp 5	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (0...3) = ((0..^3) ∪ {3})
73		fzo0to3tp 13658	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (0..^3) = {0, 1, 2}
74	73	uneq1i 4113	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((0..^3) ∪ {3}) = ({0, 1, 2} ∪ {3})
75	72, 74	eqtri 2754	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ (0...3) = ({0, 1, 2} ∪ {3})
76	35, 75	eqtrdi 2782	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((♯‘𝐹) = 3 → (0...(♯‘𝐹)) = ({0, 1, 2} ∪ {3}))
77	76	adantl 481	. . . . . . . . . . . . . . . . . . . 20 ⊢ (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (0...(♯‘𝐹)) = ({0, 1, 2} ∪ {3}))
78	68, 77	sylan9eq 2786	. . . . . . . . . . . . . . . . . . 19 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → dom 𝑃 = ({0, 1, 2} ∪ {3}))
79	78	imaeq2d 6014	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃 “ dom 𝑃) = (𝑃 “ ({0, 1, 2} ∪ {3})))
80		imadmrn 6024	. . . . . . . . . . . . . . . . . 18 ⊢ (𝑃 “ dom 𝑃) = ran 𝑃
81		imaundi 6102	. . . . . . . . . . . . . . . . . 18 ⊢ (𝑃 “ ({0, 1, 2} ∪ {3})) = ((𝑃 “ {0, 1, 2}) ∪ (𝑃 “ {3}))
82	79, 80, 81	3eqtr3g 2789	. . . . . . . . . . . . . . . . 17 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ran 𝑃 = ((𝑃 “ {0, 1, 2}) ∪ (𝑃 “ {3})))
83		ffn 6657	. . . . . . . . . . . . . . . . . . . 20 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → 𝑃 Fn (0...(♯‘𝐹)))
84	83	adantr 480	. . . . . . . . . . . . . . . . . . 19 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 𝑃 Fn (0...(♯‘𝐹)))
85	84, 37, 48, 62	fnimatpd 6912	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃 “ {0, 1, 2}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
86		nn0fz0 13531	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (3 ∈ ℕ₀ ↔ 3 ∈ (0...3))
87	32, 86	mpbi 230	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ 3 ∈ (0...3)
88	87, 35	eleqtrrid 2838	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((♯‘𝐹) = 3 → 3 ∈ (0...(♯‘𝐹)))
89	88	adantl 481	. . . . . . . . . . . . . . . . . . . 20 ⊢ (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → 3 ∈ (0...(♯‘𝐹)))
90		fnsnfv 6907	. . . . . . . . . . . . . . . . . . . 20 ⊢ ((𝑃 Fn (0...(♯‘𝐹)) ∧ 3 ∈ (0...(♯‘𝐹))) → {(𝑃‘3)} = (𝑃 “ {3}))
91	83, 89, 90	syl2an 596	. . . . . . . . . . . . . . . . . . 19 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → {(𝑃‘3)} = (𝑃 “ {3}))
92	91	eqcomd 2737	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃 “ {3}) = {(𝑃‘3)})
93	85, 92	uneq12d 4118	. . . . . . . . . . . . . . . . 17 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ((𝑃 “ {0, 1, 2}) ∪ (𝑃 “ {3})) = ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}))
94		fveq2 6828	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((♯‘𝐹) = 3 → (𝑃‘(♯‘𝐹)) = (𝑃‘3))
95	94	eqeq2d 2742	. . . . . . . . . . . . . . . . . . . 20 ⊢ ((♯‘𝐹) = 3 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ↔ (𝑃‘0) = (𝑃‘3)))
96		sneq 4585	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((𝑃‘3) = (𝑃‘0) → {(𝑃‘3)} = {(𝑃‘0)})
97	96	eqcoms 2739	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝑃‘0) = (𝑃‘3) → {(𝑃‘3)} = {(𝑃‘0)})
98	97	uneq2d 4117	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((𝑃‘0) = (𝑃‘3) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}) = ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘0)}))
99		snsstp1 4767	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ {(𝑃‘0)} ⊆ {(𝑃‘0), (𝑃‘1), (𝑃‘2)}
100	99	a1i 11	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝑃‘0) = (𝑃‘3) → {(𝑃‘0)} ⊆ {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
101		ssequn2 4138	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ({(𝑃‘0)} ⊆ {(𝑃‘0), (𝑃‘1), (𝑃‘2)} ↔ ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘0)}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
102	100, 101	sylib 218	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((𝑃‘0) = (𝑃‘3) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘0)}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
103	98, 102	eqtrd 2766	. . . . . . . . . . . . . . . . . . . 20 ⊢ ((𝑃‘0) = (𝑃‘3) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
104	95, 103	biimtrdi 253	. . . . . . . . . . . . . . . . . . 19 ⊢ ((♯‘𝐹) = 3 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)}))
105	104	impcom 407	. . . . . . . . . . . . . . . . . 18 ⊢ (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
106	105	adantl 481	. . . . . . . . . . . . . . . . 17 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
107	82, 93, 106	3eqtrd 2770	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
108	107	ex 412	. . . . . . . . . . . . . . 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 481	. . . . . . . . . . . . 13 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)}))
111	110	imp 406	. . . . . . . . . . . 12 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
112		breq2 5097	. . . . . . . . . . . . . . . 16 ⊢ ((♯‘𝐹) = 3 → (1 ≤ (♯‘𝐹) ↔ 1 ≤ 3))
113	44, 112	mpbiri 258	. . . . . . . . . . . . . . 15 ⊢ ((♯‘𝐹) = 3 → 1 ≤ (♯‘𝐹))
114	113	ad2antll 729	. . . . . . . . . . . . . 14 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 1 ≤ (♯‘𝐹))
115	2	ad2antrr 726	. . . . . . . . . . . . . 14 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 𝐹(Cycles‘𝐺)𝑃)
116		cyclnumvtx 29785	. . . . . . . . . . . . . 14 ⊢ ((1 ≤ (♯‘𝐹) ∧ 𝐹(Cycles‘𝐺)𝑃) → (♯‘ran 𝑃) = (♯‘𝐹))
117	114, 115, 116	syl2anc 584	. . . . . . . . . . . . 13 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (♯‘ran 𝑃) = (♯‘𝐹))
118	1	ad2antrr 726	. . . . . . . . . . . . 13 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (♯‘𝐹) = 3)
119	117, 118	eqtrd 2766	. . . . . . . . . . . 12 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (♯‘ran 𝑃) = 3)
120		cycl3grtri.g	. . . . . . . . . . . . 13 ⊢ (𝜑 → 𝐺 ∈ UPGraph)
121		cycl3grtrilem 48051	. . . . . . . . . . . . 13 ⊢ (((𝐺 ∈ UPGraph ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺)))
122	120, 121	sylanl1 680	. . . . . . . . . . . 12 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺)))
123	111, 119, 122	3jca 1128	. . . . . . . . . . 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 3590	. . . . . . . . . 10 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ∃𝑥 ∈ (Vtx‘𝐺)∃𝑦 ∈ (Vtx‘𝐺)∃𝑧 ∈ (Vtx‘𝐺)(ran 𝑃 = {𝑥, 𝑦, 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({𝑥, 𝑦} ∈ (Edg‘𝐺) ∧ {𝑥, 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺))))
125		eqid 2731	. . . . . . . . . . 11 ⊢ (Edg‘𝐺) = (Edg‘𝐺)
126	29, 125	isgrtri 48048	. . . . . . . . . 10 ⊢ (ran 𝑃 ∈ (GrTriangles‘𝐺) ↔ ∃𝑥 ∈ (Vtx‘𝐺)∃𝑦 ∈ (Vtx‘𝐺)∃𝑧 ∈ (Vtx‘𝐺)(ran 𝑃 = {𝑥, 𝑦, 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({𝑥, 𝑦} ∈ (Edg‘𝐺) ∧ {𝑥, 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺))))
127	124, 126	sylibr 234	. . . . . . . . 9 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ran 𝑃 ∈ (GrTriangles‘𝐺))
128	127	exp32 420	. . . . . . . 8 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) → ((♯‘𝐹) = 3 → ran 𝑃 ∈ (GrTriangles‘𝐺))))
129	128	com23 86	. . . . . . 7 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → ((♯‘𝐹) = 3 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) → ran 𝑃 ∈ (GrTriangles‘𝐺))))
130	129	expcom 413	. . . . . 6 ⊢ (𝐹(Paths‘𝐺)𝑃 → (𝜑 → ((♯‘𝐹) = 3 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) → ran 𝑃 ∈ (GrTriangles‘𝐺)))))
131	130	com24 95	. . . . 5 ⊢ (𝐹(Paths‘𝐺)𝑃 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) → ((♯‘𝐹) = 3 → (𝜑 → ran 𝑃 ∈ (GrTriangles‘𝐺)))))
132	131	imp 406	. . . 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 395 ∧ w3a 1086 = wceq 1541 ∈ wcel 2111 ∃wrex 3056 ∪ cun 3895 ⊆ wss 3897 {csn 4575 {cpr 4577 {ctp 4579 class class class wbr 5093 dom cdm 5619 ran crn 5620 “ cima 5622 Fn wfn 6482 ⟶wf 6483 ‘cfv 6487 (class class class)co 7352 0cc0 11012 1c1 11013 ≤ cle 11153 2c2 12186 3c3 12187 ℕ₀cn0 12387 ℤ_≥cuz 12738 ...cfz 13413 ..^cfzo 13560 ♯chash 14243 Vtxcvtx 28981 Edgcedg 29032 UPGraphcupgr 29065 Walkscwlks 29582 Pathscpths 29695 Cyclesccycls 29770 GrTrianglescgrtri 48042

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1796 ax-4 1810 ax-5 1911 ax-6 1968 ax-7 2009 ax-8 2113 ax-9 2121 ax-10 2144 ax-11 2160 ax-12 2180 ax-ext 2703 ax-rep 5219 ax-sep 5236 ax-nul 5246 ax-pow 5305 ax-pr 5372 ax-un 7674 ax-cnex 11068 ax-resscn 11069 ax-1cn 11070 ax-icn 11071 ax-addcl 11072 ax-addrcl 11073 ax-mulcl 11074 ax-mulrcl 11075 ax-mulcom 11076 ax-addass 11077 ax-mulass 11078 ax-distr 11079 ax-i2m1 11080 ax-1ne0 11081 ax-1rid 11082 ax-rnegex 11083 ax-rrecex 11084 ax-cnre 11085 ax-pre-lttri 11086 ax-pre-lttrn 11087 ax-pre-ltadd 11088 ax-pre-mulgt0 11089

This theorem depends on definitions: df-bi 207 df-an 396 df-or 848 df-ifp 1063 df-3or 1087 df-3an 1088 df-tru 1544 df-fal 1554 df-ex 1781 df-nf 1785 df-sb 2068 df-mo 2535 df-eu 2564 df-clab 2710 df-cleq 2723 df-clel 2806 df-nfc 2881 df-ne 2929 df-nel 3033 df-ral 3048 df-rex 3057 df-reu 3347 df-rab 3396 df-v 3438 df-sbc 3737 df-csb 3846 df-dif 3900 df-un 3902 df-in 3904 df-ss 3914 df-pss 3917 df-nul 4283 df-if 4475 df-pw 4551 df-sn 4576 df-pr 4578 df-tp 4580 df-op 4582 df-uni 4859 df-int 4898 df-iun 4943 df-br 5094 df-opab 5156 df-mpt 5175 df-tr 5201 df-id 5514 df-eprel 5519 df-po 5527 df-so 5528 df-fr 5572 df-we 5574 df-xp 5625 df-rel 5626 df-cnv 5627 df-co 5628 df-dm 5629 df-rn 5630 df-res 5631 df-ima 5632 df-pred 6254 df-ord 6315 df-on 6316 df-lim 6317 df-suc 6318 df-iota 6443 df-fun 6489 df-fn 6490 df-f 6491 df-f1 6492 df-fo 6493 df-f1o 6494 df-fv 6495 df-riota 7309 df-ov 7355 df-oprab 7356 df-mpo 7357 df-om 7803 df-1st 7927 df-2nd 7928 df-frecs 8217 df-wrecs 8248 df-recs 8297 df-rdg 8335 df-1o 8391 df-2o 8392 df-3o 8393 df-oadd 8395 df-er 8628 df-map 8758 df-pm 8759 df-en 8876 df-dom 8877 df-sdom 8878 df-fin 8879 df-dju 9800 df-card 9838 df-pnf 11154 df-mnf 11155 df-xr 11156 df-ltxr 11157 df-le 11158 df-sub 11352 df-neg 11353 df-nn 12132 df-2 12194 df-3 12195 df-n0 12388 df-xnn0 12461 df-z 12475 df-uz 12739 df-fz 13414 df-fzo 13561 df-hash 14244 df-word 14427 df-edg 29033 df-uhgr 29043 df-upgr 29067 df-wlks 29585 df-trls 29676 df-pths 29699 df-cycls 29772 df-grtri 48043

This theorem is referenced by: (None)

W3C validator