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 48507

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 29928	. . . 4 ⊢ (𝐹(Cycles‘𝐺)𝑃 → (𝐹(Paths‘𝐺)𝑃 ∧ (𝑃‘0) = (𝑃‘(♯‘𝐹))))
4		tpeq1 4691	. . . . . . . . . . . . 13 ⊢ (𝑥 = (𝑃‘0) → {𝑥, 𝑦, 𝑧} = {(𝑃‘0), 𝑦, 𝑧})
5	4	eqeq2d 2763	. . . . . . . . . . . 12 ⊢ (𝑥 = (𝑃‘0) → (ran 𝑃 = {𝑥, 𝑦, 𝑧} ↔ ran 𝑃 = {(𝑃‘0), 𝑦, 𝑧}))
6		preq1 4682	. . . . . . . . . . . . . 14 ⊢ (𝑥 = (𝑃‘0) → {𝑥, 𝑦} = {(𝑃‘0), 𝑦})
7	6	eleq1d 2837	. . . . . . . . . . . . 13 ⊢ (𝑥 = (𝑃‘0) → ({𝑥, 𝑦} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), 𝑦} ∈ (Edg‘𝐺)))
8		preq1 4682	. . . . . . . . . . . . . 14 ⊢ (𝑥 = (𝑃‘0) → {𝑥, 𝑧} = {(𝑃‘0), 𝑧})
9	8	eleq1d 2837	. . . . . . . . . . . . 13 ⊢ (𝑥 = (𝑃‘0) → ({𝑥, 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺)))
10	7, 9	3anbi12d 1448	. . . . . . . . . . . 12 ⊢ (𝑥 = (𝑃‘0) → (({𝑥, 𝑦} ∈ (Edg‘𝐺) ∧ {𝑥, 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺)) ↔ ({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺))))
11	5, 10	3anbi13d 1449	. . . . . . . . . . 11 ⊢ (𝑥 = (𝑃‘0) → ((ran 𝑃 = {𝑥, 𝑦, 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({𝑥, 𝑦} ∈ (Edg‘𝐺) ∧ {𝑥, 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺))) ↔ (ran 𝑃 = {(𝑃‘0), 𝑦, 𝑧} ∧ (♯‘ran 𝑃) = 3 ∧ ({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺)))))
12		tpeq2 4692	. . . . . . . . . . . . 13 ⊢ (𝑦 = (𝑃‘1) → {(𝑃‘0), 𝑦, 𝑧} = {(𝑃‘0), (𝑃‘1), 𝑧})
13	12	eqeq2d 2763	. . . . . . . . . . . 12 ⊢ (𝑦 = (𝑃‘1) → (ran 𝑃 = {(𝑃‘0), 𝑦, 𝑧} ↔ ran 𝑃 = {(𝑃‘0), (𝑃‘1), 𝑧}))
14		preq2 4683	. . . . . . . . . . . . . 14 ⊢ (𝑦 = (𝑃‘1) → {(𝑃‘0), 𝑦} = {(𝑃‘0), (𝑃‘1)})
15	14	eleq1d 2837	. . . . . . . . . . . . 13 ⊢ (𝑦 = (𝑃‘1) → ({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺)))
16		preq1 4682	. . . . . . . . . . . . . 14 ⊢ (𝑦 = (𝑃‘1) → {𝑦, 𝑧} = {(𝑃‘1), 𝑧})
17	16	eleq1d 2837	. . . . . . . . . . . . 13 ⊢ (𝑦 = (𝑃‘1) → ({𝑦, 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘1), 𝑧} ∈ (Edg‘𝐺)))
18	15, 17	3anbi13d 1449	. . . . . . . . . . . 12 ⊢ (𝑦 = (𝑃‘1) → (({(𝑃‘0), 𝑦} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {𝑦, 𝑧} ∈ (Edg‘𝐺)) ↔ ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), 𝑧} ∈ (Edg‘𝐺))))
19	13, 18	3anbi13d 1449	. . . . . . . . . . 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 4693	. . . . . . . . . . . . 13 ⊢ (𝑧 = (𝑃‘2) → {(𝑃‘0), (𝑃‘1), 𝑧} = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
21	20	eqeq2d 2763	. . . . . . . . . . . 12 ⊢ (𝑧 = (𝑃‘2) → (ran 𝑃 = {(𝑃‘0), (𝑃‘1), 𝑧} ↔ ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)}))
22		preq2 4683	. . . . . . . . . . . . . 14 ⊢ (𝑧 = (𝑃‘2) → {(𝑃‘0), 𝑧} = {(𝑃‘0), (𝑃‘2)})
23	22	eleq1d 2837	. . . . . . . . . . . . 13 ⊢ (𝑧 = (𝑃‘2) → ({(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺)))
24		preq2 4683	. . . . . . . . . . . . . 14 ⊢ (𝑧 = (𝑃‘2) → {(𝑃‘1), 𝑧} = {(𝑃‘1), (𝑃‘2)})
25	24	eleq1d 2837	. . . . . . . . . . . . 13 ⊢ (𝑧 = (𝑃‘2) → ({(𝑃‘1), 𝑧} ∈ (Edg‘𝐺) ↔ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺)))
26	23, 25	3anbi23d 1450	. . . . . . . . . . . 12 ⊢ (𝑧 = (𝑃‘2) → (({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), 𝑧} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), 𝑧} ∈ (Edg‘𝐺)) ↔ ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺))))
27	21, 26	3anbi13d 1449	. . . . . . . . . . 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 29860	. . . . . . . . . . . . . 14 ⊢ (𝐹(Paths‘𝐺)𝑃 → 𝐹(Walks‘𝐺)𝑃)
29		eqid 2752	. . . . . . . . . . . . . . 15 ⊢ (Vtx‘𝐺) = (Vtx‘𝐺)
30	29	wlkp 29752	. . . . . . . . . . . . . 14 ⊢ (𝐹(Walks‘𝐺)𝑃 → 𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺))
31		simpl 485	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺))
32		3nn0 12485	. . . . . . . . . . . . . . . . . . 19 ⊢ 3 ∈ ℕ₀
33		0elfz 13615	. . . . . . . . . . . . . . . . . . 19 ⊢ (3 ∈ ℕ₀ → 0 ∈ (0...3))
34	32, 33	ax-mp 5	. . . . . . . . . . . . . . . . . 18 ⊢ 0 ∈ (0...3)
35		oveq2 7389	. . . . . . . . . . . . . . . . . 18 ⊢ ((♯‘𝐹) = 3 → (0...(♯‘𝐹)) = (0...3))
36	34, 35	eleqtrrid 2859	. . . . . . . . . . . . . . . . 17 ⊢ ((♯‘𝐹) = 3 → 0 ∈ (0...(♯‘𝐹)))
37	36	ad2antll 737	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 0 ∈ (0...(♯‘𝐹)))
38	31, 37	ffvelcdmd 7051	. . . . . . . . . . . . . . 15 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘0) ∈ (Vtx‘𝐺))
39	38	ex 415	. . . . . . . . . . . . . 14 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘0) ∈ (Vtx‘𝐺)))
40	28, 30, 39	3syl 18	. . . . . . . . . . . . 13 ⊢ (𝐹(Paths‘𝐺)𝑃 → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘0) ∈ (Vtx‘𝐺)))
41	40	adantl 484	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘0) ∈ (Vtx‘𝐺)))
42	41	imp 409	. . . . . . . . . . 11 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘0) ∈ (Vtx‘𝐺))
43		1nn0 12483	. . . . . . . . . . . . . . . . . . 19 ⊢ 1 ∈ ℕ₀
44		1le3 12418	. . . . . . . . . . . . . . . . . . 19 ⊢ 1 ≤ 3
45		elfz2nn0 13609	. . . . . . . . . . . . . . . . . . 19 ⊢ (1 ∈ (0...3) ↔ (1 ∈ ℕ₀ ∧ 3 ∈ ℕ₀ ∧ 1 ≤ 3))
46	43, 32, 44, 45	mpbir3an 1351	. . . . . . . . . . . . . . . . . 18 ⊢ 1 ∈ (0...3)
47	46, 35	eleqtrrid 2859	. . . . . . . . . . . . . . . . 17 ⊢ ((♯‘𝐹) = 3 → 1 ∈ (0...(♯‘𝐹)))
48	47	ad2antll 737	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 1 ∈ (0...(♯‘𝐹)))
49	31, 48	ffvelcdmd 7051	. . . . . . . . . . . . . . 15 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘1) ∈ (Vtx‘𝐺))
50	49	ex 415	. . . . . . . . . . . . . 14 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘1) ∈ (Vtx‘𝐺)))
51	28, 30, 50	3syl 18	. . . . . . . . . . . . 13 ⊢ (𝐹(Paths‘𝐺)𝑃 → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘1) ∈ (Vtx‘𝐺)))
52	51	adantl 484	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘1) ∈ (Vtx‘𝐺)))
53	52	imp 409	. . . . . . . . . . 11 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘1) ∈ (Vtx‘𝐺))
54		2nn0 12484	. . . . . . . . . . . . . . . . . . 19 ⊢ 2 ∈ ℕ₀
55		2re 12278	. . . . . . . . . . . . . . . . . . . 20 ⊢ 2 ∈ ℝ
56		3re 12284	. . . . . . . . . . . . . . . . . . . 20 ⊢ 3 ∈ ℝ
57		2lt3 12377	. . . . . . . . . . . . . . . . . . . 20 ⊢ 2 < 3
58	55, 56, 57	ltleii 11292	. . . . . . . . . . . . . . . . . . 19 ⊢ 2 ≤ 3
59		elfz2nn0 13609	. . . . . . . . . . . . . . . . . . 19 ⊢ (2 ∈ (0...3) ↔ (2 ∈ ℕ₀ ∧ 3 ∈ ℕ₀ ∧ 2 ≤ 3))
60	54, 32, 58, 59	mpbir3an 1351	. . . . . . . . . . . . . . . . . 18 ⊢ 2 ∈ (0...3)
61	60, 35	eleqtrrid 2859	. . . . . . . . . . . . . . . . 17 ⊢ ((♯‘𝐹) = 3 → 2 ∈ (0...(♯‘𝐹)))
62	61	ad2antll 737	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 2 ∈ (0...(♯‘𝐹)))
63	31, 62	ffvelcdmd 7051	. . . . . . . . . . . . . . 15 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘2) ∈ (Vtx‘𝐺))
64	63	ex 415	. . . . . . . . . . . . . 14 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘2) ∈ (Vtx‘𝐺)))
65	28, 30, 64	3syl 18	. . . . . . . . . . . . 13 ⊢ (𝐹(Paths‘𝐺)𝑃 → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘2) ∈ (Vtx‘𝐺)))
66	65	adantl 484	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (𝑃‘2) ∈ (Vtx‘𝐺)))
67	66	imp 409	. . . . . . . . . . 11 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃‘2) ∈ (Vtx‘𝐺))
68		fdm 6686	. . . . . . . . . . . . . . . . . . . 20 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → dom 𝑃 = (0...(♯‘𝐹)))
69		elnn0uz 12866	. . . . . . . . . . . . . . . . . . . . . . . . 25 ⊢ (3 ∈ ℕ₀ ↔ 3 ∈ (ℤ_≥‘0))
70	32, 69	mpbi 232	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ 3 ∈ (ℤ_≥‘0)
71		fzisfzounsn 13772	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (3 ∈ (ℤ_≥‘0) → (0...3) = ((0..^3) ∪ {3}))
72	70, 71	ax-mp 5	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (0...3) = ((0..^3) ∪ {3})
73		fzo0to3tp 13744	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (0..^3) = {0, 1, 2}
74	73	uneq1i 4108	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((0..^3) ∪ {3}) = ({0, 1, 2} ∪ {3})
75	72, 74	eqtri 2775	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ (0...3) = ({0, 1, 2} ∪ {3})
76	35, 75	eqtrdi 2803	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((♯‘𝐹) = 3 → (0...(♯‘𝐹)) = ({0, 1, 2} ∪ {3}))
77	76	adantl 484	. . . . . . . . . . . . . . . . . . . 20 ⊢ (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → (0...(♯‘𝐹)) = ({0, 1, 2} ∪ {3}))
78	68, 77	sylan9eq 2807	. . . . . . . . . . . . . . . . . . 19 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → dom 𝑃 = ({0, 1, 2} ∪ {3}))
79	78	imaeq2d 6035	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃 “ dom 𝑃) = (𝑃 “ ({0, 1, 2} ∪ {3})))
80		imadmrn 6045	. . . . . . . . . . . . . . . . . 18 ⊢ (𝑃 “ dom 𝑃) = ran 𝑃
81		imaundi 6120	. . . . . . . . . . . . . . . . . 18 ⊢ (𝑃 “ ({0, 1, 2} ∪ {3})) = ((𝑃 “ {0, 1, 2}) ∪ (𝑃 “ {3}))
82	79, 80, 81	3eqtr3g 2810	. . . . . . . . . . . . . . . . 17 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ran 𝑃 = ((𝑃 “ {0, 1, 2}) ∪ (𝑃 “ {3})))
83		ffn 6676	. . . . . . . . . . . . . . . . . . . 20 ⊢ (𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) → 𝑃 Fn (0...(♯‘𝐹)))
84	83	adantr 483	. . . . . . . . . . . . . . . . . . 19 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 𝑃 Fn (0...(♯‘𝐹)))
85	84, 37, 48, 62	fnimatpd 6936	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃 “ {0, 1, 2}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
86		nn0fz0 13616	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (3 ∈ ℕ₀ ↔ 3 ∈ (0...3))
87	32, 86	mpbi 232	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ 3 ∈ (0...3)
88	87, 35	eleqtrrid 2859	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((♯‘𝐹) = 3 → 3 ∈ (0...(♯‘𝐹)))
89	88	adantl 484	. . . . . . . . . . . . . . . . . . . 20 ⊢ (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → 3 ∈ (0...(♯‘𝐹)))
90		fnsnfv 6931	. . . . . . . . . . . . . . . . . . . 20 ⊢ ((𝑃 Fn (0...(♯‘𝐹)) ∧ 3 ∈ (0...(♯‘𝐹))) → {(𝑃‘3)} = (𝑃 “ {3}))
91	83, 89, 90	syl2an 604	. . . . . . . . . . . . . . . . . . 19 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → {(𝑃‘3)} = (𝑃 “ {3}))
92	91	eqcomd 2758	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (𝑃 “ {3}) = {(𝑃‘3)})
93	85, 92	uneq12d 4113	. . . . . . . . . . . . . . . . 17 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ((𝑃 “ {0, 1, 2}) ∪ (𝑃 “ {3})) = ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}))
94		fveq2 6852	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((♯‘𝐹) = 3 → (𝑃‘(♯‘𝐹)) = (𝑃‘3))
95	94	eqeq2d 2763	. . . . . . . . . . . . . . . . . . . 20 ⊢ ((♯‘𝐹) = 3 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ↔ (𝑃‘0) = (𝑃‘3)))
96		sneq 4582	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((𝑃‘3) = (𝑃‘0) → {(𝑃‘3)} = {(𝑃‘0)})
97	96	eqcoms 2760	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝑃‘0) = (𝑃‘3) → {(𝑃‘3)} = {(𝑃‘0)})
98	97	uneq2d 4112	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((𝑃‘0) = (𝑃‘3) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}) = ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘0)}))
99		snsstp1 4764	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ {(𝑃‘0)} ⊆ {(𝑃‘0), (𝑃‘1), (𝑃‘2)}
100	99	a1i 11	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝑃‘0) = (𝑃‘3) → {(𝑃‘0)} ⊆ {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
101		ssequn2 4132	. . . . . . . . . . . . . . . . . . . . . 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 2787	. . . . . . . . . . . . . . . . . . . 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 410	. . . . . . . . . . . . . . . . . 18 ⊢ (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
106	105	adantl 484	. . . . . . . . . . . . . . . . 17 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ({(𝑃‘0), (𝑃‘1), (𝑃‘2)} ∪ {(𝑃‘3)}) = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
107	82, 93, 106	3eqtrd 2791	. . . . . . . . . . . . . . . 16 ⊢ ((𝑃:(0...(♯‘𝐹))⟶(Vtx‘𝐺) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
108	107	ex 415	. . . . . . . . . . . . . . 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 484	. . . . . . . . . . . . 13 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → (((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3) → ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)}))
111	110	imp 409	. . . . . . . . . . . 12 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ran 𝑃 = {(𝑃‘0), (𝑃‘1), (𝑃‘2)})
112		breq2 5094	. . . . . . . . . . . . . . . 16 ⊢ ((♯‘𝐹) = 3 → (1 ≤ (♯‘𝐹) ↔ 1 ≤ 3))
113	44, 112	mpbiri 260	. . . . . . . . . . . . . . 15 ⊢ ((♯‘𝐹) = 3 → 1 ≤ (♯‘𝐹))
114	113	ad2antll 737	. . . . . . . . . . . . . 14 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 1 ≤ (♯‘𝐹))
115	2	ad2antrr 734	. . . . . . . . . . . . . 14 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → 𝐹(Cycles‘𝐺)𝑃)
116		cyclnumvtx 29935	. . . . . . . . . . . . . 14 ⊢ ((1 ≤ (♯‘𝐹) ∧ 𝐹(Cycles‘𝐺)𝑃) → (♯‘ran 𝑃) = (♯‘𝐹))
117	114, 115, 116	syl2anc 592	. . . . . . . . . . . . 13 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (♯‘ran 𝑃) = (♯‘𝐹))
118	1	ad2antrr 734	. . . . . . . . . . . . 13 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (♯‘𝐹) = 3)
119	117, 118	eqtrd 2787	. . . . . . . . . . . 12 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → (♯‘ran 𝑃) = 3)
120		cycl3grtri.g	. . . . . . . . . . . . 13 ⊢ (𝜑 → 𝐺 ∈ UPGraph)
121		cycl3grtrilem 48506	. . . . . . . . . . . . 13 ⊢ (((𝐺 ∈ UPGraph ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺)))
122	120, 121	sylanl1 688	. . . . . . . . . . . 12 ⊢ (((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) ∧ ((𝑃‘0) = (𝑃‘(♯‘𝐹)) ∧ (♯‘𝐹) = 3)) → ({(𝑃‘0), (𝑃‘1)} ∈ (Edg‘𝐺) ∧ {(𝑃‘0), (𝑃‘2)} ∈ (Edg‘𝐺) ∧ {(𝑃‘1), (𝑃‘2)} ∈ (Edg‘𝐺)))
123	111, 119, 122	3jca 1137	. . . . . . . . . . 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 2752	. . . . . . . . . . 11 ⊢ (Edg‘𝐺) = (Edg‘𝐺)
126	29, 125	isgrtri 48503	. . . . . . . . . 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 423	. . . . . . . 8 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) → ((♯‘𝐹) = 3 → ran 𝑃 ∈ (GrTriangles‘𝐺))))
129	128	com23 86	. . . . . . 7 ⊢ ((𝜑 ∧ 𝐹(Paths‘𝐺)𝑃) → ((♯‘𝐹) = 3 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) → ran 𝑃 ∈ (GrTriangles‘𝐺))))
130	129	expcom 416	. . . . . 6 ⊢ (𝐹(Paths‘𝐺)𝑃 → (𝜑 → ((♯‘𝐹) = 3 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) → ran 𝑃 ∈ (GrTriangles‘𝐺)))))
131	130	com24 95	. . . . 5 ⊢ (𝐹(Paths‘𝐺)𝑃 → ((𝑃‘0) = (𝑃‘(♯‘𝐹)) → ((♯‘𝐹) = 3 → (𝜑 → ran 𝑃 ∈ (GrTriangles‘𝐺)))))
132	131	imp 409	. . . 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 398 ∧ w3a 1095 = wceq 1550 ∈ wcel 2132 ∃wrex 3076 ∪ cun 3893 ⊆ wss 3895 {csn 4572 {cpr 4574 {ctp 4576 class class class wbr 5090 dom cdm 5636 ran crn 5637 “ cima 5639 Fn wfn 6501 ⟶wf 6502 ‘cfv 6506 (class class class)co 7381 0cc0 11059 1c1 11060 ≤ cle 11203 2c2 12258 3c3 12259 ℕ₀cn0 12467 ℤ_≥cuz 12825 ...cfz 13498 ..^cfzo 13645 ♯chash 14329 Vtxcvtx 29132 Edgcedg 29183 UPGraphcupgr 29216 Walkscwlks 29732 Pathscpths 29845 Cyclesccycls 29920 GrTrianglescgrtri 48497

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1805 ax-4 1819 ax-5 1920 ax-6 1977 ax-7 2018 ax-8 2134 ax-9 2142 ax-10 2165 ax-11 2181 ax-12 2202 ax-ext 2724 ax-rep 5217 ax-sep 5236 ax-nul 5246 ax-pow 5312 ax-pr 5380 ax-un 7703 ax-cnex 11115 ax-resscn 11116 ax-1cn 11117 ax-icn 11118 ax-addcl 11119 ax-addrcl 11120 ax-mulcl 11121 ax-mulrcl 11122 ax-mulcom 11123 ax-addass 11124 ax-mulass 11125 ax-distr 11126 ax-i2m1 11127 ax-1ne0 11128 ax-1rid 11129 ax-rnegex 11130 ax-rrecex 11131 ax-cnre 11132 ax-pre-lttri 11133 ax-pre-lttrn 11134 ax-pre-ltadd 11135 ax-pre-mulgt0 11136

This theorem depends on definitions: df-bi 209 df-an 399 df-or 857 df-ifp 1072 df-3or 1096 df-3an 1097 df-tru 1553 df-fal 1563 df-ex 1790 df-nf 1794 df-sb 2081 df-mo 2556 df-eu 2586 df-clab 2731 df-cleq 2744 df-clel 2827 df-nfc 2901 df-ne 2948 df-nel 3052 df-ral 3067 df-rex 3077 df-reu 3358 df-rab 3405 df-v 3446 df-sbc 3736 df-csb 3844 df-dif 3898 df-un 3900 df-in 3902 df-ss 3912 df-pss 3915 df-nul 4277 df-if 4471 df-pw 4547 df-sn 4573 df-pr 4575 df-tp 4577 df-op 4579 df-uni 4856 df-int 4896 df-iun 4941 df-br 5091 df-opab 5153 df-mpt 5172 df-tr 5198 df-id 5531 df-eprel 5536 df-po 5544 df-so 5545 df-fr 5589 df-we 5591 df-xp 5642 df-rel 5643 df-cnv 5644 df-co 5645 df-dm 5646 df-rn 5647 df-res 5648 df-ima 5649 df-pred 6273 df-ord 6334 df-on 6335 df-lim 6336 df-suc 6337 df-iota 6462 df-fun 6508 df-fn 6509 df-f 6510 df-f1 6511 df-fo 6512 df-f1o 6513 df-fv 6514 df-riota 7338 df-ov 7384 df-oprab 7385 df-mpo 7386 df-om 7832 df-1st 7955 df-2nd 7956 df-frecs 8246 df-wrecs 8277 df-recs 8326 df-rdg 8365 df-1o 8421 df-2o 8422 df-3o 8423 df-oadd 8425 df-er 8662 df-map 8794 df-pm 8795 df-en 8913 df-dom 8914 df-sdom 8915 df-fin 8916 df-dju 9845 df-card 9883 df-pnf 11204 df-mnf 11205 df-xr 11206 df-ltxr 11207 df-le 11208 df-sub 11402 df-neg 11403 df-nn 12197 df-2 12266 df-3 12267 df-n0 12468 df-xnn0 12541 df-z 12555 df-uz 12826 df-fz 13499 df-fzo 13646 df-hash 14330 df-word 14513 df-edg 29184 df-uhgr 29194 df-upgr 29218 df-wlks 29735 df-trls 29826 df-pths 29849 df-cycls 29922 df-grtri 48498

This theorem is referenced by: (None)

W3C validator