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 48381

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 29850	. . . 4 ⊢ (𝐹(Cycles‘𝐺)𝑃 → (𝐹(Paths‘𝐺)𝑃 ∧ (𝑃‘0) = (𝑃‘(♯‘𝐹))))
4		tpeq1 4687	. . . . . . . . . . . . 13 ⊢ (𝑥 = (𝑃‘0) → {𝑥, 𝑦, 𝑧} = {(𝑃‘0), 𝑦, 𝑧})
5	4	eqeq2d 2748	. . . . . . . . . . . 12 ⊢ (𝑥 = (𝑃‘0) → (ran 𝑃 = {𝑥, 𝑦, 𝑧} ↔ ran 𝑃 = {(𝑃‘0), 𝑦, 𝑧}))
6		preq1 4678	. . . . . . . . . . . . . 14 ⊢ (𝑥 = (𝑃‘0) → {𝑥, 𝑦} = {(𝑃‘0), 𝑦})
7	6	eleq1d 2822	. . . . . . . . . . . . 13 ⊢ (𝑥 = (𝑃‘0) → ({𝑥, 𝑦} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), 𝑦} ∈ (Edg‘𝐺)))
8		preq1 4678	. . . . . . . . . . . . . 14 ⊢ (𝑥 = (𝑃‘0) → {𝑥, 𝑧} = {(𝑃‘0), 𝑧})
9	8	eleq1d 2822	. . . . . . . . . . . . 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 4688	. . . . . . . . . . . . 13 ⊢ (𝑦 = (𝑃‘1) → {(𝑃‘0), 𝑦, 𝑧} = {(𝑃‘0), (𝑃‘1), 𝑧})
13	12	eqeq2d 2748	. . . . . . . . . . . 12 ⊢ (𝑦 = (𝑃‘1) → (ran 𝑃 = {(𝑃‘0), 𝑦, 𝑧} ↔ ran 𝑃 = {(𝑃‘0), (𝑃‘1), 𝑧}))
14		preq2 4679	. . . . . . . . . . . . . 14 ⊢ (𝑦 = (𝑃‘1) → {(𝑃‘0), 𝑦} = {(𝑃‘0), (𝑃‘1)})
15	14	eleq1d 2822	. . . . . . . . . . . . 13 ⊢ (𝑦 = (𝑃‘1) → ({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺)))
16		preq1 4678	. . . . . . . . . . . . . 14 ⊢ (𝑦 = (𝑃‘1) → {𝑦, 𝑧} = {(𝑃‘1), 𝑧})
17	16	eleq1d 2822	. . . . . . . . . . . . 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 4689	. . . . . . . . . . . . 13 ⊢ (𝑧 = (𝑃‘2) → {(𝑃‘0), (𝑃‘1), 𝑧} = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
21	20	eqeq2d 2748	. . . . . . . . . . . 12 ⊢ (𝑧 = (𝑃‘2) → (ran 𝑃 = {(𝑃‘0), (𝑃‘1), 𝑧} ↔ ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)}))
22		preq2 4679	. . . . . . . . . . . . . 14 ⊢ (𝑧 = (𝑃‘2) → {(𝑃‘0), 𝑧} = {(𝑃‘0), (𝑃‘2)})
23	22	eleq1d 2822	. . . . . . . . . . . . 13 ⊢ (𝑧 = (𝑃‘2) → ({(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺)))
24		preq2 4679	. . . . . . . . . . . . . 14 ⊢ (𝑧 = (𝑃‘2) → {(𝑃‘1), 𝑧} = {(𝑃‘1), (𝑃‘2)})
25	24	eleq1d 2822	. . . . . . . . . . . . 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 29782	. . . . . . . . . . . . . 14 ⊢ (𝐹(Paths‘𝐺)𝑃 → 𝐹(Walks‘𝐺)𝑃)
29		eqid 2737	. . . . . . . . . . . . . . 15 ⊢ (Vtx‘𝐺) = (Vtx‘𝐺)
30	29	wlkp 29674	. . . . . . . . . . . . . 14 ⊢ (𝐹(Walks‘𝐺)𝑃 → 𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺))
31		simpl 482	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺))
32		3nn0 12420	. . . . . . . . . . . . . . . . . . 19 ⊢ 3 ∈ ℕ₀
33		0elfz 13541	. . . . . . . . . . . . . . . . . . 19 ⊢ (3 ∈ ℕ₀ → 0 ∈ (0...3))
34	32, 33	ax-mp 5	. . . . . . . . . . . . . . . . . 18 ⊢ 0 ∈ (0...3)
35		oveq2 7366	. . . . . . . . . . . . . . . . . 18 ⊢ ((♯‘𝐹) = 3 → (0...(♯‘𝐹)) = (0...3))
36	34, 35	eleqtrrid 2844	. . . . . . . . . . . . . . . . 17 ⊢ ((♯‘𝐹) = 3 → 0 ∈ (0...(♯‘𝐹)))
37	36	ad2antll 730	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 0 ∈ (0...(♯‘𝐹)))
38	31, 37	ffvelcdmd 7029	. . . . . . . . . . . . . . 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 12418	. . . . . . . . . . . . . . . . . . 19 ⊢ 1 ∈ ℕ₀
44		1le3 12353	. . . . . . . . . . . . . . . . . . 19 ⊢ 1 ≤ 3
45		elfz2nn0 13535	. . . . . . . . . . . . . . . . . . 19 ⊢ (1 ∈ (0...3) ↔ (1 ∈ ℕ₀ ∧ 3 ∈ ℕ₀ ∧ 1 ≤ 3))
46	43, 32, 44, 45	mpbir3an 1343	. . . . . . . . . . . . . . . . . 18 ⊢ 1 ∈ (0...3)
47	46, 35	eleqtrrid 2844	. . . . . . . . . . . . . . . . 17 ⊢ ((♯‘𝐹) = 3 → 1 ∈ (0...(♯‘𝐹)))
48	47	ad2antll 730	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 1 ∈ (0...(♯‘𝐹)))
49	31, 48	ffvelcdmd 7029	. . . . . . . . . . . . . . 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 12419	. . . . . . . . . . . . . . . . . . 19 ⊢ 2 ∈ ℕ₀
55		2re 12220	. . . . . . . . . . . . . . . . . . . 20 ⊢ 2 ∈ ℝ
56		3re 12226	. . . . . . . . . . . . . . . . . . . 20 ⊢ 3 ∈ ℝ
57		2lt3 12313	. . . . . . . . . . . . . . . . . . . 20 ⊢ 2 < 3
58	55, 56, 57	ltleii 11257	. . . . . . . . . . . . . . . . . . 19 ⊢ 2 ≤ 3
59		elfz2nn0 13535	. . . . . . . . . . . . . . . . . . 19 ⊢ (2 ∈ (0...3) ↔ (2 ∈ ℕ₀ ∧ 3 ∈ ℕ₀ ∧ 2 ≤ 3))
60	54, 32, 58, 59	mpbir3an 1343	. . . . . . . . . . . . . . . . . 18 ⊢ 2 ∈ (0...3)
61	60, 35	eleqtrrid 2844	. . . . . . . . . . . . . . . . 17 ⊢ ((♯‘𝐹) = 3 → 2 ∈ (0...(♯‘𝐹)))
62	61	ad2antll 730	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 2 ∈ (0...(♯‘𝐹)))
63	31, 62	ffvelcdmd 7029	. . . . . . . . . . . . . . 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 6669	. . . . . . . . . . . . . . . . . . . 20 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → dom 𝑃 = (0...(♯‘𝐹)))
69		elnn0uz 12793	. . . . . . . . . . . . . . . . . . . . . . . . 25 ⊢ (3 ∈ ℕ₀ ↔ 3 ∈ (ℤ_≥‘0))
70	32, 69	mpbi 230	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ 3 ∈ (ℤ_≥‘0)
71		fzisfzounsn 13697	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (3 ∈ (ℤ_≥‘0) → (0...3) = ((0..^3) ∪ {3}))
72	70, 71	ax-mp 5	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (0...3) = ((0..^3) ∪ {3})
73		fzo0to3tp 13669	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (0..^3) = {0, 1, 2}
74	73	uneq1i 4105	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((0..^3) ∪ {3}) = ({0, 1, 2} ∪ {3})
75	72, 74	eqtri 2760	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ (0...3) = ({0, 1, 2} ∪ {3})
76	35, 75	eqtrdi 2788	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((♯‘𝐹) = 3 → (0...(♯‘𝐹)) = ({0, 1, 2} ∪ {3}))
77	76	adantl 481	. . . . . . . . . . . . . . . . . . . 20 ⊢ (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (0...(♯‘𝐹)) = ({0, 1, 2} ∪ {3}))
78	68, 77	sylan9eq 2792	. . . . . . . . . . . . . . . . . . 19 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → dom 𝑃 = ({0, 1, 2} ∪ {3}))
79	78	imaeq2d 6017	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃 “ dom 𝑃) = (𝑃 “ ({0, 1, 2} ∪ {3})))
80		imadmrn 6027	. . . . . . . . . . . . . . . . . 18 ⊢ (𝑃 “ dom 𝑃) = ran 𝑃
81		imaundi 6105	. . . . . . . . . . . . . . . . . 18 ⊢ (𝑃 “ ({0, 1, 2} ∪ {3})) = ((𝑃 “ {0, 1, 2}) ∪ (𝑃 “ {3}))
82	79, 80, 81	3eqtr3g 2795	. . . . . . . . . . . . . . . . 17 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ran 𝑃 = ((𝑃 “ {0, 1, 2}) ∪ (𝑃 “ {3})))
83		ffn 6660	. . . . . . . . . . . . . . . . . . . 20 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → 𝑃 Fn (0...(♯‘𝐹)))
84	83	adantr 480	. . . . . . . . . . . . . . . . . . 19 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 𝑃 Fn (0...(♯‘𝐹)))
85	84, 37, 48, 62	fnimatpd 6916	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃 “ {0, 1, 2}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
86		nn0fz0 13542	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (3 ∈ ℕ₀ ↔ 3 ∈ (0...3))
87	32, 86	mpbi 230	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ 3 ∈ (0...3)
88	87, 35	eleqtrrid 2844	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((♯‘𝐹) = 3 → 3 ∈ (0...(♯‘𝐹)))
89	88	adantl 481	. . . . . . . . . . . . . . . . . . . 20 ⊢ (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → 3 ∈ (0...(♯‘𝐹)))
90		fnsnfv 6911	. . . . . . . . . . . . . . . . . . . 20 ⊢ ((𝑃 Fn (0...(♯‘𝐹)) ∧ 3 ∈ (0...(♯‘𝐹))) → {(𝑃‘3)} = (𝑃 “ {3}))
91	83, 89, 90	syl2an 597	. . . . . . . . . . . . . . . . . . 19 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → {(𝑃‘3)} = (𝑃 “ {3}))
92	91	eqcomd 2743	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃 “ {3}) = {(𝑃‘3)})
93	85, 92	uneq12d 4110	. . . . . . . . . . . . . . . . 17 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ((𝑃 “ {0, 1, 2}) ∪ (𝑃 “ {3})) = ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}))
94		fveq2 6832	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((♯‘𝐹) = 3 → (𝑃‘(♯‘𝐹)) = (𝑃‘3))
95	94	eqeq2d 2748	. . . . . . . . . . . . . . . . . . . 20 ⊢ ((♯‘𝐹) = 3 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ↔ (𝑃‘0) = (𝑃‘3)))
96		sneq 4578	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((𝑃‘3) = (𝑃‘0) → {(𝑃‘3)} = {(𝑃‘0)})
97	96	eqcoms 2745	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝑃‘0) = (𝑃‘3) → {(𝑃‘3)} = {(𝑃‘0)})
98	97	uneq2d 4109	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((𝑃‘0) = (𝑃‘3) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}) = ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘0)}))
99		snsstp1 4760	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ {(𝑃‘0)} ⊆ {(𝑃‘0), (𝑃‘1), (𝑃‘2)}
100	99	a1i 11	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝑃‘0) = (𝑃‘3) → {(𝑃‘0)} ⊆ {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
101		ssequn2 4130	. . . . . . . . . . . . . . . . . . . . . 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 2772	. . . . . . . . . . . . . . . . . . . 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 2776	. . . . . . . . . . . . . . . 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 5090	. . . . . . . . . . . . . . . 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 29857	. . . . . . . . . . . . . 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 2772	. . . . . . . . . . . 12 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (♯‘ran 𝑃) = 3)
120		cycl3grtri.g	. . . . . . . . . . . . 13 ⊢ (𝜑 → 𝐺 ∈ UPGraph)
121		cycl3grtrilem 48380	. . . . . . . . . . . . 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 3583	. . . . . . . . . 10 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ∃𝑥 ∈ (Vtx‘𝐺)∃𝑦 ∈ (Vtx‘𝐺)∃𝑧 ∈ (Vtx‘𝐺)(ran 𝑃 = {𝑥, 𝑦, 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({𝑥, 𝑦} ∈ (Edg‘𝐺) ∧ {𝑥, 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺))))
125		eqid 2737	. . . . . . . . . . 11 ⊢ (Edg‘𝐺) = (Edg‘𝐺)
126	29, 125	isgrtri 48377	. . . . . . . . . 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 3062 ∪ cun 3888 ⊆ wss 3890 {csn 4568 {cpr 4570 {ctp 4572 class class class wbr 5086 dom cdm 5622 ran crn 5623 “ cima 5625 Fn wfn 6485 ⟶wf 6486 ‘cfv 6490 (class class class)co 7358 0cc0 11027 1c1 11028 ≤ cle 11168 2c2 12201 3c3 12202 ℕ₀cn0 12402 ℤ_≥cuz 12752 ...cfz 13424 ..^cfzo 13571 ♯chash 14254 Vtxcvtx 29053 Edgcedg 29104 UPGraphcupgr 29137 Walkscwlks 29654 Pathscpths 29767 Cyclesccycls 29842 GrTrianglescgrtri 48371

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 2185 ax-ext 2709 ax-rep 5212 ax-sep 5231 ax-nul 5241 ax-pow 5300 ax-pr 5368 ax-un 7680 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 2540 df-eu 2570 df-clab 2716 df-cleq 2729 df-clel 2812 df-nfc 2886 df-ne 2934 df-nel 3038 df-ral 3053 df-rex 3063 df-reu 3344 df-rab 3391 df-v 3432 df-sbc 3730 df-csb 3839 df-dif 3893 df-un 3895 df-in 3897 df-ss 3907 df-pss 3910 df-nul 4275 df-if 4468 df-pw 4544 df-sn 4569 df-pr 4571 df-tp 4573 df-op 4575 df-uni 4852 df-int 4891 df-iun 4936 df-br 5087 df-opab 5149 df-mpt 5168 df-tr 5194 df-id 5517 df-eprel 5522 df-po 5530 df-so 5531 df-fr 5575 df-we 5577 df-xp 5628 df-rel 5629 df-cnv 5630 df-co 5631 df-dm 5632 df-rn 5633 df-res 5634 df-ima 5635 df-pred 6257 df-ord 6318 df-on 6319 df-lim 6320 df-suc 6321 df-iota 6446 df-fun 6492 df-fn 6493 df-f 6494 df-f1 6495 df-fo 6496 df-f1o 6497 df-fv 6498 df-riota 7315 df-ov 7361 df-oprab 7362 df-mpo 7363 df-om 7809 df-1st 7933 df-2nd 7934 df-frecs 8222 df-wrecs 8253 df-recs 8302 df-rdg 8340 df-1o 8396 df-2o 8397 df-3o 8398 df-oadd 8400 df-er 8634 df-map 8766 df-pm 8767 df-en 8885 df-dom 8886 df-sdom 8887 df-fin 8888 df-dju 9814 df-card 9852 df-pnf 11169 df-mnf 11170 df-xr 11171 df-ltxr 11172 df-le 11173 df-sub 11367 df-neg 11368 df-nn 12147 df-2 12209 df-3 12210 df-n0 12403 df-xnn0 12476 df-z 12490 df-uz 12753 df-fz 13425 df-fzo 13572 df-hash 14255 df-word 14438 df-edg 29105 df-uhgr 29115 df-upgr 29139 df-wlks 29657 df-trls 29748 df-pths 29771 df-cycls 29844 df-grtri 48372

This theorem is referenced by: (None)

W3C validator