Theorem isconngr 29442

Description: The property of being a connected graph. (Contributed by Alexander van der Vekens, 2-Dec-2017.) (Revised by AV, 15-Feb-2021.)

Hypothesis

Ref	Expression
isconngr.v	⊢ 𝑉 = (Vtx‘𝐺)

Assertion

Ref	Expression
isconngr	⊢ (𝐺 ∈ 𝑊 → (𝐺 ∈ ConnGraph ↔ ∀𝑘 ∈ 𝑉 ∀𝑛 ∈ 𝑉 ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝐺)𝑛)𝑝))

Distinct variable groups:   𝑓,𝑘,𝑛,𝑝,𝐺   𝑘,𝑉,𝑛

Allowed substitution hints:   𝑉(𝑓,𝑝)   𝑊(𝑓,𝑘,𝑛,𝑝)

Proof of Theorem isconngr

Dummy variables 𝑔 ℎ 𝑣 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		df-conngr 29440	. . 3 ⊢ ConnGraph = {𝑔 ∣ [(Vtx‘𝑔) / 𝑣]∀𝑘 ∈ 𝑣 ∀𝑛 ∈ 𝑣 ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝}
2	1	eleq2i 2826	. 2 ⊢ (𝐺 ∈ ConnGraph ↔ 𝐺 ∈ {𝑔 ∣ [(Vtx‘𝑔) / 𝑣]∀𝑘 ∈ 𝑣 ∀𝑛 ∈ 𝑣 ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝})
3		fvex 6905	. . . . . 6 ⊢ (Vtx‘𝑔) ∈ V
4		raleq 3323	. . . . . . 7 ⊢ (𝑣 = (Vtx‘𝑔) → (∀𝑛 ∈ 𝑣 ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝 ↔ ∀𝑛 ∈ (Vtx‘𝑔)∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝))
5	4	raleqbi1dv 3334	. . . . . 6 ⊢ (𝑣 = (Vtx‘𝑔) → (∀𝑘 ∈ 𝑣 ∀𝑛 ∈ 𝑣 ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝 ↔ ∀𝑘 ∈ (Vtx‘𝑔)∀𝑛 ∈ (Vtx‘𝑔)∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝))
6	3, 5	sbcie 3821	. . . . 5 ⊢ ([(Vtx‘𝑔) / 𝑣]∀𝑘 ∈ 𝑣 ∀𝑛 ∈ 𝑣 ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝 ↔ ∀𝑘 ∈ (Vtx‘𝑔)∀𝑛 ∈ (Vtx‘𝑔)∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝)
7	6	abbii 2803	. . . 4 ⊢ {𝑔 ∣ [(Vtx‘𝑔) / 𝑣]∀𝑘 ∈ 𝑣 ∀𝑛 ∈ 𝑣 ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝} = {𝑔 ∣ ∀𝑘 ∈ (Vtx‘𝑔)∀𝑛 ∈ (Vtx‘𝑔)∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝}
8	7	eleq2i 2826	. . 3 ⊢ (𝐺 ∈ {𝑔 ∣ [(Vtx‘𝑔) / 𝑣]∀𝑘 ∈ 𝑣 ∀𝑛 ∈ 𝑣 ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝} ↔ 𝐺 ∈ {𝑔 ∣ ∀𝑘 ∈ (Vtx‘𝑔)∀𝑛 ∈ (Vtx‘𝑔)∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝})
9		fveq2 6892	. . . . . 6 ⊢ (ℎ = 𝐺 → (Vtx‘ℎ) = (Vtx‘𝐺))
10		isconngr.v	. . . . . 6 ⊢ 𝑉 = (Vtx‘𝐺)
11	9, 10	eqtr4di 2791	. . . . 5 ⊢ (ℎ = 𝐺 → (Vtx‘ℎ) = 𝑉)
12		fveq2 6892	. . . . . . . . 9 ⊢ (ℎ = 𝐺 → (PathsOn‘ℎ) = (PathsOn‘𝐺))
13	12	oveqd 7426	. . . . . . . 8 ⊢ (ℎ = 𝐺 → (𝑘(PathsOn‘ℎ)𝑛) = (𝑘(PathsOn‘𝐺)𝑛))
14	13	breqd 5160	. . . . . . 7 ⊢ (ℎ = 𝐺 → (𝑓(𝑘(PathsOn‘ℎ)𝑛)𝑝 ↔ 𝑓(𝑘(PathsOn‘𝐺)𝑛)𝑝))
15	14	2exbidv 1928	. . . . . 6 ⊢ (ℎ = 𝐺 → (∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘ℎ)𝑛)𝑝 ↔ ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝐺)𝑛)𝑝))
16	11, 15	raleqbidv 3343	. . . . 5 ⊢ (ℎ = 𝐺 → (∀𝑛 ∈ (Vtx‘ℎ)∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘ℎ)𝑛)𝑝 ↔ ∀𝑛 ∈ 𝑉 ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝐺)𝑛)𝑝))
17	11, 16	raleqbidv 3343	. . . 4 ⊢ (ℎ = 𝐺 → (∀𝑘 ∈ (Vtx‘ℎ)∀𝑛 ∈ (Vtx‘ℎ)∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘ℎ)𝑛)𝑝 ↔ ∀𝑘 ∈ 𝑉 ∀𝑛 ∈ 𝑉 ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝐺)𝑛)𝑝))
18		fveq2 6892	. . . . . 6 ⊢ (𝑔 = ℎ → (Vtx‘𝑔) = (Vtx‘ℎ))
19		fveq2 6892	. . . . . . . . . 10 ⊢ (𝑔 = ℎ → (PathsOn‘𝑔) = (PathsOn‘ℎ))
20	19	oveqd 7426	. . . . . . . . 9 ⊢ (𝑔 = ℎ → (𝑘(PathsOn‘𝑔)𝑛) = (𝑘(PathsOn‘ℎ)𝑛))
21	20	breqd 5160	. . . . . . . 8 ⊢ (𝑔 = ℎ → (𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝 ↔ 𝑓(𝑘(PathsOn‘ℎ)𝑛)𝑝))
22	21	2exbidv 1928	. . . . . . 7 ⊢ (𝑔 = ℎ → (∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝 ↔ ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘ℎ)𝑛)𝑝))
23	18, 22	raleqbidv 3343	. . . . . 6 ⊢ (𝑔 = ℎ → (∀𝑛 ∈ (Vtx‘𝑔)∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝 ↔ ∀𝑛 ∈ (Vtx‘ℎ)∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘ℎ)𝑛)𝑝))
24	18, 23	raleqbidv 3343	. . . . 5 ⊢ (𝑔 = ℎ → (∀𝑘 ∈ (Vtx‘𝑔)∀𝑛 ∈ (Vtx‘𝑔)∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝 ↔ ∀𝑘 ∈ (Vtx‘ℎ)∀𝑛 ∈ (Vtx‘ℎ)∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘ℎ)𝑛)𝑝))
25	24	cbvabv 2806	. . . 4 ⊢ {𝑔 ∣ ∀𝑘 ∈ (Vtx‘𝑔)∀𝑛 ∈ (Vtx‘𝑔)∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝} = {ℎ ∣ ∀𝑘 ∈ (Vtx‘ℎ)∀𝑛 ∈ (Vtx‘ℎ)∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘ℎ)𝑛)𝑝}
26	17, 25	elab2g 3671	. . 3 ⊢ (𝐺 ∈ 𝑊 → (𝐺 ∈ {𝑔 ∣ ∀𝑘 ∈ (Vtx‘𝑔)∀𝑛 ∈ (Vtx‘𝑔)∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝} ↔ ∀𝑘 ∈ 𝑉 ∀𝑛 ∈ 𝑉 ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝐺)𝑛)𝑝))
27	8, 26	bitrid 283	. 2 ⊢ (𝐺 ∈ 𝑊 → (𝐺 ∈ {𝑔 ∣ [(Vtx‘𝑔) / 𝑣]∀𝑘 ∈ 𝑣 ∀𝑛 ∈ 𝑣 ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝑔)𝑛)𝑝} ↔ ∀𝑘 ∈ 𝑉 ∀𝑛 ∈ 𝑉 ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝐺)𝑛)𝑝))
28	2, 27	bitrid 283	1 ⊢ (𝐺 ∈ 𝑊 → (𝐺 ∈ ConnGraph ↔ ∀𝑘 ∈ 𝑉 ∀𝑛 ∈ 𝑉 ∃𝑓∃𝑝 𝑓(𝑘(PathsOn‘𝐺)𝑛)𝑝))

Syntax hints:   → wi 4   ↔ wb 205   = wceq 1542  ∃wex 1782   ∈ wcel 2107  {cab 2710  ∀wral 3062  [wsbc 3778   class class class wbr 5149  ‘cfv 6544  (class class class)co 7409  Vtxcvtx 28256  PathsOncpthson 28971  ConnGraphcconngr 29439

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1798  ax-4 1812  ax-5 1914  ax-6 1972  ax-7 2012  ax-8 2109  ax-9 2117  ax-ext 2704  ax-nul 5307

This theorem depends on definitions:  df-bi 206  df-an 398  df-or 847  df-3an 1090  df-tru 1545  df-fal 1555  df-ex 1783  df-sb 2069  df-clab 2711  df-cleq 2725  df-clel 2811  df-ne 2942  df-ral 3063  df-rex 3072  df-rab 3434  df-v 3477  df-sbc 3779  df-dif 3952  df-un 3954  df-in 3956  df-ss 3966  df-nul 4324  df-if 4530  df-sn 4630  df-pr 4632  df-op 4636  df-uni 4910  df-br 5150  df-iota 6496  df-fv 6552  df-ov 7412  df-conngr 29440

This theorem is referenced by:  0conngr  29445  0vconngr  29446  1conngr  29447  conngrv2edg  29448