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 48411

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 29849	. . . 4 ⊢ (𝐹(Cycles‘𝐺)𝑃 → (𝐹(Paths‘𝐺)𝑃 ∧ (𝑃‘0) = (𝑃‘(♯‘𝐹))))
4		tpeq1 4676	. . . . . . . . . . . . 13 ⊢ (𝑥 = (𝑃‘0) → {𝑥, 𝑦, 𝑧} = {(𝑃‘0), 𝑦, 𝑧})
5	4	eqeq2d 2746	. . . . . . . . . . . 12 ⊢ (𝑥 = (𝑃‘0) → (ran 𝑃 = {𝑥, 𝑦, 𝑧} ↔ ran 𝑃 = {(𝑃‘0), 𝑦, 𝑧}))
6		preq1 4667	. . . . . . . . . . . . . 14 ⊢ (𝑥 = (𝑃‘0) → {𝑥, 𝑦} = {(𝑃‘0), 𝑦})
7	6	eleq1d 2820	. . . . . . . . . . . . 13 ⊢ (𝑥 = (𝑃‘0) → ({𝑥, 𝑦} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), 𝑦} ∈ (Edg‘𝐺)))
8		preq1 4667	. . . . . . . . . . . . . 14 ⊢ (𝑥 = (𝑃‘0) → {𝑥, 𝑧} = {(𝑃‘0), 𝑧})
9	8	eleq1d 2820	. . . . . . . . . . . . 13 ⊢ (𝑥 = (𝑃‘0) → ({𝑥, 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺)))
10	7, 9	3anbi12d 1440	. . . . . . . . . . . 12 ⊢ (𝑥 = (𝑃‘0) → (({𝑥, 𝑦} ∈ (Edg‘𝐺) ∧ {𝑥, 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺)) ↔ ({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺))))
11	5, 10	3anbi13d 1441	. . . . . . . . . . 11 ⊢ (𝑥 = (𝑃‘0) → ((ran 𝑃 = {𝑥, 𝑦, 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({𝑥, 𝑦} ∈ (Edg‘𝐺) ∧ {𝑥, 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺))) ↔ (ran 𝑃 = {(𝑃‘0), 𝑦, 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺)))))
12		tpeq2 4677	. . . . . . . . . . . . 13 ⊢ (𝑦 = (𝑃‘1) → {(𝑃‘0), 𝑦, 𝑧} = {(𝑃‘0), (𝑃‘1), 𝑧})
13	12	eqeq2d 2746	. . . . . . . . . . . 12 ⊢ (𝑦 = (𝑃‘1) → (ran 𝑃 = {(𝑃‘0), 𝑦, 𝑧} ↔ ran 𝑃 = {(𝑃‘0), (𝑃‘1), 𝑧}))
14		preq2 4668	. . . . . . . . . . . . . 14 ⊢ (𝑦 = (𝑃‘1) → {(𝑃‘0), 𝑦} = {(𝑃‘0), (𝑃‘1)})
15	14	eleq1d 2820	. . . . . . . . . . . . 13 ⊢ (𝑦 = (𝑃‘1) → ({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺)))
16		preq1 4667	. . . . . . . . . . . . . 14 ⊢ (𝑦 = (𝑃‘1) → {𝑦, 𝑧} = {(𝑃‘1), 𝑧})
17	16	eleq1d 2820	. . . . . . . . . . . . 13 ⊢ (𝑦 = (𝑃‘1) → ({𝑦, 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘1), 𝑧} ∈ (Edg‘𝐺)))
18	15, 17	3anbi13d 1441	. . . . . . . . . . . 12 ⊢ (𝑦 = (𝑃‘1) → (({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺)) ↔ ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), 𝑧} ∈ (Edg‘𝐺))))
19	13, 18	3anbi13d 1441	. . . . . . . . . . 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 4678	. . . . . . . . . . . . 13 ⊢ (𝑧 = (𝑃‘2) → {(𝑃‘0), (𝑃‘1), 𝑧} = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
21	20	eqeq2d 2746	. . . . . . . . . . . 12 ⊢ (𝑧 = (𝑃‘2) → (ran 𝑃 = {(𝑃‘0), (𝑃‘1), 𝑧} ↔ ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)}))
22		preq2 4668	. . . . . . . . . . . . . 14 ⊢ (𝑧 = (𝑃‘2) → {(𝑃‘0), 𝑧} = {(𝑃‘0), (𝑃‘2)})
23	22	eleq1d 2820	. . . . . . . . . . . . 13 ⊢ (𝑧 = (𝑃‘2) → ({(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺)))
24		preq2 4668	. . . . . . . . . . . . . 14 ⊢ (𝑧 = (𝑃‘2) → {(𝑃‘1), 𝑧} = {(𝑃‘1), (𝑃‘2)})
25	24	eleq1d 2820	. . . . . . . . . . . . 13 ⊢ (𝑧 = (𝑃‘2) → ({(𝑃‘1), 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺)))
26	23, 25	3anbi23d 1442	. . . . . . . . . . . 12 ⊢ (𝑧 = (𝑃‘2) → (({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), 𝑧} ∈ (Edg‘𝐺)) ↔ ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺))))
27	21, 26	3anbi13d 1441	. . . . . . . . . . 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 29781	. . . . . . . . . . . . . 14 ⊢ (𝐹(Paths‘𝐺)𝑃 → 𝐹(Walks‘𝐺)𝑃)
29		eqid 2735	. . . . . . . . . . . . . . 15 ⊢ (Vtx‘𝐺) = (Vtx‘𝐺)
30	29	wlkp 29673	. . . . . . . . . . . . . 14 ⊢ (𝐹(Walks‘𝐺)𝑃 → 𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺))
31		simpl 482	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺))
32		3nn0 12444	. . . . . . . . . . . . . . . . . . 19 ⊢ 3 ∈ ℕ₀
33		0elfz 13567	. . . . . . . . . . . . . . . . . . 19 ⊢ (3 ∈ ℕ₀ → 0 ∈ (0...3))
34	32, 33	ax-mp 5	. . . . . . . . . . . . . . . . . 18 ⊢ 0 ∈ (0...3)
35		oveq2 7364	. . . . . . . . . . . . . . . . . 18 ⊢ ((♯‘𝐹) = 3 → (0...(♯‘𝐹)) = (0...3))
36	34, 35	eleqtrrid 2842	. . . . . . . . . . . . . . . . 17 ⊢ ((♯‘𝐹) = 3 → 0 ∈ (0...(♯‘𝐹)))
37	36	ad2antll 730	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 0 ∈ (0...(♯‘𝐹)))
38	31, 37	ffvelcdmd 7026	. . . . . . . . . . . . . . 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 12442	. . . . . . . . . . . . . . . . . . 19 ⊢ 1 ∈ ℕ₀
44		1le3 12377	. . . . . . . . . . . . . . . . . . 19 ⊢ 1 ≤ 3
45		elfz2nn0 13561	. . . . . . . . . . . . . . . . . . 19 ⊢ (1 ∈ (0...3) ↔ (1 ∈ ℕ₀ ∧ 3 ∈ ℕ₀ ∧ 1 ≤ 3))
46	43, 32, 44, 45	mpbir3an 1343	. . . . . . . . . . . . . . . . . 18 ⊢ 1 ∈ (0...3)
47	46, 35	eleqtrrid 2842	. . . . . . . . . . . . . . . . 17 ⊢ ((♯‘𝐹) = 3 → 1 ∈ (0...(♯‘𝐹)))
48	47	ad2antll 730	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 1 ∈ (0...(♯‘𝐹)))
49	31, 48	ffvelcdmd 7026	. . . . . . . . . . . . . . 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 12443	. . . . . . . . . . . . . . . . . . 19 ⊢ 2 ∈ ℕ₀
55		2re 12244	. . . . . . . . . . . . . . . . . . . 20 ⊢ 2 ∈ ℝ
56		3re 12250	. . . . . . . . . . . . . . . . . . . 20 ⊢ 3 ∈ ℝ
57		2lt3 12337	. . . . . . . . . . . . . . . . . . . 20 ⊢ 2 < 3
58	55, 56, 57	ltleii 11258	. . . . . . . . . . . . . . . . . . 19 ⊢ 2 ≤ 3
59		elfz2nn0 13561	. . . . . . . . . . . . . . . . . . 19 ⊢ (2 ∈ (0...3) ↔ (2 ∈ ℕ₀ ∧ 3 ∈ ℕ₀ ∧ 2 ≤ 3))
60	54, 32, 58, 59	mpbir3an 1343	. . . . . . . . . . . . . . . . . 18 ⊢ 2 ∈ (0...3)
61	60, 35	eleqtrrid 2842	. . . . . . . . . . . . . . . . 17 ⊢ ((♯‘𝐹) = 3 → 2 ∈ (0...(♯‘𝐹)))
62	61	ad2antll 730	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 2 ∈ (0...(♯‘𝐹)))
63	31, 62	ffvelcdmd 7026	. . . . . . . . . . . . . . 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 12818	. . . . . . . . . . . . . . . . . . . . . . . . 25 ⊢ (3 ∈ ℕ₀ ↔ 3 ∈ (ℤ_≥‘0))
70	32, 69	mpbi 230	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ 3 ∈ (ℤ_≥‘0)
71		fzisfzounsn 13724	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (3 ∈ (ℤ_≥‘0) → (0...3) = ((0..^3) ∪ {3}))
72	70, 71	ax-mp 5	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (0...3) = ((0..^3) ∪ {3})
73		fzo0to3tp 13696	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (0..^3) = {0, 1, 2}
74	73	uneq1i 4096	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((0..^3) ∪ {3}) = ({0, 1, 2} ∪ {3})
75	72, 74	eqtri 2758	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ (0...3) = ({0, 1, 2} ∪ {3})
76	35, 75	eqtrdi 2786	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((♯‘𝐹) = 3 → (0...(♯‘𝐹)) = ({0, 1, 2} ∪ {3}))
77	76	adantl 481	. . . . . . . . . . . . . . . . . . . 20 ⊢ (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (0...(♯‘𝐹)) = ({0, 1, 2} ∪ {3}))
78	68, 77	sylan9eq 2790	. . . . . . . . . . . . . . . . . . 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 2793	. . . . . . . . . . . . . . . . 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 6913	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃 “ {0, 1, 2}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
86		nn0fz0 13568	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (3 ∈ ℕ₀ ↔ 3 ∈ (0...3))
87	32, 86	mpbi 230	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ 3 ∈ (0...3)
88	87, 35	eleqtrrid 2842	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((♯‘𝐹) = 3 → 3 ∈ (0...(♯‘𝐹)))
89	88	adantl 481	. . . . . . . . . . . . . . . . . . . 20 ⊢ (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → 3 ∈ (0...(♯‘𝐹)))
90		fnsnfv 6908	. . . . . . . . . . . . . . . . . . . 20 ⊢ ((𝑃 Fn (0...(♯‘𝐹)) ∧ 3 ∈ (0...(♯‘𝐹))) → {(𝑃‘3)} = (𝑃 “ {3}))
91	83, 89, 90	syl2an 597	. . . . . . . . . . . . . . . . . . 19 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → {(𝑃‘3)} = (𝑃 “ {3}))
92	91	eqcomd 2741	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃 “ {3}) = {(𝑃‘3)})
93	85, 92	uneq12d 4101	. . . . . . . . . . . . . . . . 17 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ((𝑃 “ {0, 1, 2}) ∪ (𝑃 “ {3})) = ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}))
94		fveq2 6829	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((♯‘𝐹) = 3 → (𝑃‘(♯‘𝐹)) = (𝑃‘3))
95	94	eqeq2d 2746	. . . . . . . . . . . . . . . . . . . 20 ⊢ ((♯‘𝐹) = 3 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ↔ (𝑃‘0) = (𝑃‘3)))
96		sneq 4567	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((𝑃‘3) = (𝑃‘0) → {(𝑃‘3)} = {(𝑃‘0)})
97	96	eqcoms 2743	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝑃‘0) = (𝑃‘3) → {(𝑃‘3)} = {(𝑃‘0)})
98	97	uneq2d 4100	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((𝑃‘0) = (𝑃‘3) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}) = ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘0)}))
99		snsstp1 4749	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ {(𝑃‘0)} ⊆ {(𝑃‘0), (𝑃‘1), (𝑃‘2)}
100	99	a1i 11	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝑃‘0) = (𝑃‘3) → {(𝑃‘0)} ⊆ {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
101		ssequn2 4120	. . . . . . . . . . . . . . . . . . . . . 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 2770	. . . . . . . . . . . . . . . . . . . 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 2774	. . . . . . . . . . . . . . . 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 5078	. . . . . . . . . . . . . . . 16 ⊢ ((♯‘𝐹) = 3 → (1 ≤ (♯‘𝐹) ↔ 1 ≤ 3))
113	44, 112	mpbiri 258	. . . . . . . . . . . . . . 15 ⊢ ((♯‘𝐹) = 3 → 1 ≤ (♯‘𝐹))
114	113	ad2antll 730	. . . . . . . . . . . . . 14 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 1 ≤ (♯‘𝐹))
115	2	ad2antrr 727	. . . . . . . . . . . . . 14 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 𝐹(Cycles‘𝐺)𝑃)
116		cyclnumvtx 29856	. . . . . . . . . . . . . 14 ⊢ ((1 ≤ (♯‘𝐹) ∧ 𝐹(Cycles‘𝐺)𝑃) → (♯‘ran 𝑃) = (♯‘𝐹))
117	114, 115, 116	syl2anc 585	. . . . . . . . . . . . 13 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (♯‘ran 𝑃) = (♯‘𝐹))
118	1	ad2antrr 727	. . . . . . . . . . . . 13 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (♯‘𝐹) = 3)
119	117, 118	eqtrd 2770	. . . . . . . . . . . 12 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (♯‘ran 𝑃) = 3)
120		cycl3grtri.g	. . . . . . . . . . . . 13 ⊢ (𝜑 → 𝐺 ∈ UPGraph)
121		cycl3grtrilem 48410	. . . . . . . . . . . . 13 ⊢ (((𝐺 ∈ UPGraph ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺)))
122	120, 121	sylanl1 681	. . . . . . . . . . . 12 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺)))
123	111, 119, 122	3jca 1129	. . . . . . . . . . 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 3580	. . . . . . . . . 10 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ∃𝑥 ∈ (Vtx‘𝐺)∃𝑦 ∈ (Vtx‘𝐺)∃𝑧 ∈ (Vtx‘𝐺)(ran 𝑃 = {𝑥, 𝑦, 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({𝑥, 𝑦} ∈ (Edg‘𝐺) ∧ {𝑥, 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺))))
125		eqid 2735	. . . . . . . . . . 11 ⊢ (Edg‘𝐺) = (Edg‘𝐺)
126	29, 125	isgrtri 48407	. . . . . . . . . 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 1087 = wceq 1542 ∈ wcel 2114 ∃wrex 3059 ∪ cun 3883 ⊆ wss 3885 {csn 4557 {cpr 4559 {ctp 4561 class class class wbr 5074 dom cdm 5620 ran crn 5621 “ cima 5623 Fn wfn 6482 ⟶wf 6483 ‘cfv 6487 (class class class)co 7356 0cc0 11027 1c1 11028 ≤ cle 11169 2c2 12225 3c3 12226 ℕ₀cn0 12426 ℤ_≥cuz 12777 ...cfz 13450 ..^cfzo 13597 ♯chash 14281 Vtxcvtx 29053 Edgcedg 29104 UPGraphcupgr 29137 Walkscwlks 29653 Pathscpths 29766 Cyclesccycls 29841 GrTrianglescgrtri 48401

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1797 ax-4 1811 ax-5 1912 ax-6 1969 ax-7 2010 ax-8 2116 ax-9 2124 ax-10 2147 ax-11 2163 ax-12 2184 ax-ext 2707 ax-rep 5201 ax-sep 5220 ax-nul 5230 ax-pow 5296 ax-pr 5364 ax-un 7678 ax-cnex 11083 ax-resscn 11084 ax-1cn 11085 ax-icn 11086 ax-addcl 11087 ax-addrcl 11088 ax-mulcl 11089 ax-mulrcl 11090 ax-mulcom 11091 ax-addass 11092 ax-mulass 11093 ax-distr 11094 ax-i2m1 11095 ax-1ne0 11096 ax-1rid 11097 ax-rnegex 11098 ax-rrecex 11099 ax-cnre 11100 ax-pre-lttri 11101 ax-pre-lttrn 11102 ax-pre-ltadd 11103 ax-pre-mulgt0 11104

This theorem depends on definitions: df-bi 207 df-an 396 df-or 849 df-ifp 1064 df-3or 1088 df-3an 1089 df-tru 1545 df-fal 1555 df-ex 1782 df-nf 1786 df-sb 2069 df-mo 2538 df-eu 2568 df-clab 2714 df-cleq 2727 df-clel 2810 df-nfc 2884 df-ne 2931 df-nel 3035 df-ral 3050 df-rex 3060 df-reu 3341 df-rab 3388 df-v 3429 df-sbc 3726 df-csb 3834 df-dif 3888 df-un 3890 df-in 3892 df-ss 3902 df-pss 3905 df-nul 4264 df-if 4457 df-pw 4533 df-sn 4558 df-pr 4560 df-tp 4562 df-op 4564 df-uni 4841 df-int 4880 df-iun 4925 df-br 5075 df-opab 5137 df-mpt 5156 df-tr 5182 df-id 5515 df-eprel 5520 df-po 5528 df-so 5529 df-fr 5573 df-we 5575 df-xp 5626 df-rel 5627 df-cnv 5628 df-co 5629 df-dm 5630 df-rn 5631 df-res 5632 df-ima 5633 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 7313 df-ov 7359 df-oprab 7360 df-mpo 7361 df-om 7807 df-1st 7931 df-2nd 7932 df-frecs 8220 df-wrecs 8251 df-recs 8300 df-rdg 8338 df-1o 8394 df-2o 8395 df-3o 8396 df-oadd 8398 df-er 8632 df-map 8764 df-pm 8765 df-en 8883 df-dom 8884 df-sdom 8885 df-fin 8886 df-dju 9814 df-card 9852 df-pnf 11170 df-mnf 11171 df-xr 11172 df-ltxr 11173 df-le 11174 df-sub 11368 df-neg 11369 df-nn 12164 df-2 12233 df-3 12234 df-n0 12427 df-xnn0 12500 df-z 12514 df-uz 12778 df-fz 13451 df-fzo 13598 df-hash 14282 df-word 14465 df-edg 29105 df-uhgr 29115 df-upgr 29139 df-wlks 29656 df-trls 29747 df-pths 29770 df-cycls 29843 df-grtri 48402

This theorem is referenced by: (None)

W3C validator