P. 310 of Theorem List - Metamath Proof Explorer

Theorem List for Metamath Proof Explorer - 30901-31000   *Has distinct variable group(s)

Type	Label	Description
Statement
Theorem	frcond4 30901*	The friendship condition, alternatively expressed by neighborhoods: in a friendship graph, the neighborhoods of two different vertices have exactly one vertex in common. (Contributed by Alexander van der Vekens, 19-Dec-2017.) (Revised by AV, 29-Mar-2021.) (Proof shortened by AV, 30-Dec-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ (𝐺 ∈ FriendGraph → ∀𝑘 ∈ 𝑉 ∀𝑙 ∈ (𝑉 ∖ {𝑘})∃𝑥 ∈ 𝑉 ((𝐺 NeighbVtx 𝑘) ∩ (𝐺 NeighbVtx 𝑙)) = {𝑥})
17.5.2  The friendship theorem for small graphs
Theorem	frgr1v 30902	Any graph with (at most) one vertex is a friendship graph. (Contributed by Alexander van der Vekens, 4-Oct-2017.) (Revised by AV, 29-Mar-2021.)
⊢ ((𝐺 ∈ USGraph ∧ (Vtx‘𝐺) = {𝑁}) → 𝐺 ∈ FriendGraph )
Theorem	nfrgr2v 30903	Any graph with two (different) vertices is not a friendship graph. (Contributed by Alexander van der Vekens, 30-Sep-2017.) (Proof shortened by Alexander van der Vekens, 13-Sep-2018.) (Revised by AV, 29-Mar-2021.)
⊢ (((𝐴 ∈ 𝑋 ∧ 𝐵 ∈ 𝑌 ∧ 𝐴 ≠ 𝐵) ∧ (Vtx‘𝐺) = {𝐴, 𝐵}) → 𝐺 ∉ FriendGraph )
Theorem	frgr3vlem1 30904*	Lemma 1 for frgr3v 30906. (Contributed by Alexander van der Vekens, 4-Oct-2017.) (Revised by AV, 29-Mar-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ (((𝐴 ∈ 𝑋 ∧ 𝐵 ∈ 𝑌 ∧ 𝐶 ∈ 𝑍) ∧ (𝐴 ≠ 𝐵 ∧ 𝐴 ≠ 𝐶 ∧ 𝐵 ≠ 𝐶) ∧ (𝑉 = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph)) → ∀𝑥∀𝑦(((𝑥 ∈ {𝐴, 𝐵, 𝐶} ∧ {{𝑥, 𝐴}, {𝑥, 𝐵}} ⊆ 𝐸) ∧ (𝑦 ∈ {𝐴, 𝐵, 𝐶} ∧ {{𝑦, 𝐴}, {𝑦, 𝐵}} ⊆ 𝐸)) → 𝑥 = 𝑦))
Theorem	frgr3vlem2 30905*	Lemma 2 for frgr3v 30906. (Contributed by Alexander van der Vekens, 4-Oct-2017.) (Revised by AV, 29-Mar-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ (((𝐴 ∈ 𝑋 ∧ 𝐵 ∈ 𝑌 ∧ 𝐶 ∈ 𝑍) ∧ (𝐴 ≠ 𝐵 ∧ 𝐴 ≠ 𝐶 ∧ 𝐵 ≠ 𝐶)) → ((𝑉 = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph) → (∃!𝑥 ∈ {𝐴, 𝐵, 𝐶} {{𝑥, 𝐴}, {𝑥, 𝐵}} ⊆ 𝐸 ↔ ({𝐶, 𝐴} ∈ 𝐸 ∧ {𝐶, 𝐵} ∈ 𝐸))))
Theorem	frgr3v 30906	Any graph with three vertices which are completely connected with each other is a friendship graph. (Contributed by Alexander van der Vekens, 5-Oct-2017.) (Revised by AV, 29-Mar-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ (((𝐴 ∈ 𝑋 ∧ 𝐵 ∈ 𝑌 ∧ 𝐶 ∈ 𝑍) ∧ (𝐴 ≠ 𝐵 ∧ 𝐴 ≠ 𝐶 ∧ 𝐵 ≠ 𝐶)) → ((𝑉 = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph) → (𝐺 ∈ FriendGraph ↔ ({𝐴, 𝐵} ∈ 𝐸 ∧ {𝐵, 𝐶} ∈ 𝐸 ∧ {𝐶, 𝐴} ∈ 𝐸))))
Theorem	1vwmgr 30907*	Every graph with one vertex (which may be connect with itself by (multiple) loops!) is a windmill graph. (Contributed by Alexander van der Vekens, 5-Oct-2017.) (Revised by AV, 31-Mar-2021.)
⊢ ((𝐴 ∈ 𝑋 ∧ 𝑉 = {𝐴}) → ∃ℎ ∈ 𝑉 ∀𝑣 ∈ (𝑉 ∖ {ℎ})({𝑣, ℎ} ∈ 𝐸 ∧ ∃!𝑤 ∈ (𝑉 ∖ {ℎ}){𝑣, 𝑤} ∈ 𝐸))
Theorem	3vfriswmgrlem 30908*	Lemma for 3vfriswmgr 30909. (Contributed by Alexander van der Vekens, 6-Oct-2017.) (Revised by AV, 31-Mar-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ (((𝐴 ∈ 𝑋 ∧ 𝐵 ∈ 𝑌 ∧ 𝐴 ≠ 𝐵) ∧ (𝑉 = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph)) → ({𝐴, 𝐵} ∈ 𝐸 → ∃!𝑤 ∈ {𝐴, 𝐵} {𝐴, 𝑤} ∈ 𝐸))
Theorem	3vfriswmgr 30909*	Every friendship graph with three (different) vertices is a windmill graph. (Contributed by Alexander van der Vekens, 6-Oct-2017.) (Revised by AV, 31-Mar-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ (((𝐴 ∈ 𝑋 ∧ 𝐵 ∈ 𝑌 ∧ 𝐶 ∈ 𝑍) ∧ (𝐴 ≠ 𝐵 ∧ 𝐴 ≠ 𝐶 ∧ 𝐵 ≠ 𝐶) ∧ 𝑉 = {𝐴, 𝐵, 𝐶}) → (𝐺 ∈ FriendGraph → ∃ℎ ∈ 𝑉 ∀𝑣 ∈ (𝑉 ∖ {ℎ})({𝑣, ℎ} ∈ 𝐸 ∧ ∃!𝑤 ∈ (𝑉 ∖ {ℎ}){𝑣, 𝑤} ∈ 𝐸)))
Theorem	1to2vfriswmgr 30910*	Every friendship graph with one or two vertices is a windmill graph. (Contributed by Alexander van der Vekens, 6-Oct-2017.) (Revised by AV, 31-Mar-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ ((𝐴 ∈ 𝑋 ∧ (𝑉 = {𝐴} ∨ 𝑉 = {𝐴, 𝐵})) → (𝐺 ∈ FriendGraph → ∃ℎ ∈ 𝑉 ∀𝑣 ∈ (𝑉 ∖ {ℎ})({𝑣, ℎ} ∈ 𝐸 ∧ ∃!𝑤 ∈ (𝑉 ∖ {ℎ}){𝑣, 𝑤} ∈ 𝐸)))
Theorem	1to3vfriswmgr 30911*	Every friendship graph with one, two or three vertices is a windmill graph. (Contributed by Alexander van der Vekens, 6-Oct-2017.) (Revised by AV, 31-Mar-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ ((𝐴 ∈ 𝑋 ∧ (𝑉 = {𝐴} ∨ 𝑉 = {𝐴, 𝐵} ∨ 𝑉 = {𝐴, 𝐵, 𝐶})) → (𝐺 ∈ FriendGraph → ∃ℎ ∈ 𝑉 ∀𝑣 ∈ (𝑉 ∖ {ℎ})({𝑣, ℎ} ∈ 𝐸 ∧ ∃!𝑤 ∈ (𝑉 ∖ {ℎ}){𝑣, 𝑤} ∈ 𝐸)))
Theorem	1to3vfriendship 30912*	The friendship theorem for small graphs: In every friendship graph with one, two or three vertices, there is a vertex which is adjacent to all other vertices. (Contributed by Alexander van der Vekens, 6-Oct-2017.) (Revised by AV, 31-Mar-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ ((𝐴 ∈ 𝑋 ∧ (𝑉 = {𝐴} ∨ 𝑉 = {𝐴, 𝐵} ∨ 𝑉 = {𝐴, 𝐵, 𝐶})) → (𝐺 ∈ FriendGraph → ∃𝑣 ∈ 𝑉 ∀𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ 𝐸))
17.5.3  Theorems according to Mertzios and Unger
Theorem	2pthfrgrrn 30913*	Between any two (different) vertices in a friendship graph is a 2-path (path of length 2), see Proposition 1(b) of [MertziosUnger] p. 153 : "A friendship graph G ..., as well as the distance between any two nodes in G is at most two". (Contributed by Alexander van der Vekens, 15-Nov-2017.) (Revised by AV, 1-Apr-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ (𝐺 ∈ FriendGraph → ∀𝑎 ∈ 𝑉 ∀𝑐 ∈ (𝑉 ∖ {𝑎})∃𝑏 ∈ 𝑉 ({𝑎, 𝑏} ∈ 𝐸 ∧ {𝑏, 𝑐} ∈ 𝐸))
Theorem	2pthfrgrrn2 30914*	Between any two (different) vertices in a friendship graph is a 2-path (path of length 2), see Proposition 1(b) of [MertziosUnger] p. 153 : "A friendship graph G ..., as well as the distance between any two nodes in G is at most two". (Contributed by Alexander van der Vekens, 16-Nov-2017.) (Revised by AV, 1-Apr-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ (𝐺 ∈ FriendGraph → ∀𝑎 ∈ 𝑉 ∀𝑐 ∈ (𝑉 ∖ {𝑎})∃𝑏 ∈ 𝑉 (({𝑎, 𝑏} ∈ 𝐸 ∧ {𝑏, 𝑐} ∈ 𝐸) ∧ (𝑎 ≠ 𝑏 ∧ 𝑏 ≠ 𝑐)))
Theorem	2pthfrgr 30915*	Between any two (different) vertices in a friendship graph, there is a 2-path (simple path of length 2), see Proposition 1(b) of [MertziosUnger] p. 153 : "A friendship graph G ..., as well as the distance between any two nodes in G is at most two". (Contributed by Alexander van der Vekens, 6-Dec-2017.) (Revised by AV, 1-Apr-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ (𝐺 ∈ FriendGraph → ∀𝑎 ∈ 𝑉 ∀𝑏 ∈ (𝑉 ∖ {𝑎})∃𝑓∃𝑝(𝑓(𝑎(SPathsOn‘𝐺)𝑏)𝑝 ∧ (♯‘𝑓) = 2))
Theorem	3cyclfrgrrn1 30916*	Every vertex in a friendship graph (with more than 1 vertex) is part of a 3-cycle. (Contributed by Alexander van der Vekens, 16-Nov-2017.) (Revised by AV, 2-Apr-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ (𝐴 ∈ 𝑉 ∧ 𝐶 ∈ 𝑉) ∧ 𝐴 ≠ 𝐶) → ∃𝑏 ∈ 𝑉 ∃𝑐 ∈ 𝑉 ({𝐴, 𝑏} ∈ 𝐸 ∧ {𝑏, 𝑐} ∈ 𝐸 ∧ {𝑐, 𝐴} ∈ 𝐸))
Theorem	3cyclfrgrrn 30917*	Every vertex in a friendship graph (with more than 1 vertex) is part of a 3-cycle. (Contributed by Alexander van der Vekens, 16-Nov-2017.) (Revised by AV, 2-Apr-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ 1 < (♯‘𝑉)) → ∀𝑎 ∈ 𝑉 ∃𝑏 ∈ 𝑉 ∃𝑐 ∈ 𝑉 ({𝑎, 𝑏} ∈ 𝐸 ∧ {𝑏, 𝑐} ∈ 𝐸 ∧ {𝑐, 𝑎} ∈ 𝐸))
Theorem	3cyclfrgrrn2 30918*	Every vertex in a friendship graph (with more than 1 vertex) is part of a 3-cycle. (Contributed by Alexander van der Vekens, 10-Dec-2017.) (Revised by AV, 2-Apr-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ 1 < (♯‘𝑉)) → ∀𝑎 ∈ 𝑉 ∃𝑏 ∈ 𝑉 ∃𝑐 ∈ 𝑉 (𝑏 ≠ 𝑐 ∧ ({𝑎, 𝑏} ∈ 𝐸 ∧ {𝑏, 𝑐} ∈ 𝐸 ∧ {𝑐, 𝑎} ∈ 𝐸)))
Theorem	3cyclfrgr 30919*	Every vertex in a friendship graph (with more than 1 vertex) is part of a 3-cycle. (Contributed by Alexander van der Vekens, 19-Nov-2017.) (Revised by AV, 2-Apr-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ 1 < (♯‘𝑉)) → ∀𝑣 ∈ 𝑉 ∃𝑓∃𝑝(𝑓(Cycles‘𝐺)𝑝 ∧ (♯‘𝑓) = 3 ∧ (𝑝‘0) = 𝑣))
Theorem	4cycl2v2nb 30920	In a (maybe degenerate) 4-cycle, two vertice have two (maybe not different) common neighbors. (Contributed by Alexander van der Vekens, 19-Nov-2017.) (Revised by AV, 2-Apr-2021.)
⊢ ((({𝐴, 𝐵} ∈ 𝐸 ∧ {𝐵, 𝐶} ∈ 𝐸) ∧ ({𝐶, 𝐷} ∈ 𝐸 ∧ {𝐷, 𝐴} ∈ 𝐸)) → ({{𝐴, 𝐵}, {𝐵, 𝐶}} ⊆ 𝐸 ∧ {{𝐴, 𝐷}, {𝐷, 𝐶}} ⊆ 𝐸))
Theorem	4cycl2vnunb 30921*	In a 4-cycle, two distinct vertices have not a unique common neighbor. (Contributed by Alexander van der Vekens, 19-Nov-2017.) (Revised by AV, 2-Apr-2021.)
⊢ ((({𝐴, 𝐵} ∈ 𝐸 ∧ {𝐵, 𝐶} ∈ 𝐸) ∧ ({𝐶, 𝐷} ∈ 𝐸 ∧ {𝐷, 𝐴} ∈ 𝐸) ∧ (𝐵 ∈ 𝑉 ∧ 𝐷 ∈ 𝑉 ∧ 𝐵 ≠ 𝐷)) → ¬ ∃!𝑥 ∈ 𝑉 {{𝐴, 𝑥}, {𝑥, 𝐶}} ⊆ 𝐸)
Theorem	n4cyclfrgr 30922	There is no 4-cycle in a friendship graph, see Proposition 1(a) of [MertziosUnger] p. 153 : "A friendship graph G contains no C4 as a subgraph ...". (Contributed by Alexander van der Vekens, 19-Nov-2017.) (Revised by AV, 2-Apr-2021.)
⊢ ((𝐺 ∈ FriendGraph ∧ 𝐹(Cycles‘𝐺)𝑃) → (♯‘𝐹) ≠ 4)
Theorem	4cyclusnfrgr 30923	A graph with a 4-cycle is not a friendhip graph. (Contributed by Alexander van der Vekens, 19-Dec-2017.) (Revised by AV, 2-Apr-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ ((𝐺 ∈ USGraph ∧ (𝐴 ∈ 𝑉 ∧ 𝐶 ∈ 𝑉 ∧ 𝐴 ≠ 𝐶) ∧ (𝐵 ∈ 𝑉 ∧ 𝐷 ∈ 𝑉 ∧ 𝐵 ≠ 𝐷)) → ((({𝐴, 𝐵} ∈ 𝐸 ∧ {𝐵, 𝐶} ∈ 𝐸) ∧ ({𝐶, 𝐷} ∈ 𝐸 ∧ {𝐷, 𝐴} ∈ 𝐸)) → 𝐺 ∉ FriendGraph ))
Theorem	frgrnbnb 30924	If two neighbors 𝑈 and 𝑊 of a vertex 𝑋 have a common neighbor 𝐴 in a friendship graph, then this common neighbor 𝐴 must be the vertex 𝑋. (Contributed by Alexander van der Vekens, 19-Dec-2017.) (Revised by AV, 2-Apr-2021.) (Proof shortened by AV, 13-Feb-2022.)
⊢ 𝐸 = (Edg‘𝐺)    &   ⊢ 𝐷 = (𝐺 NeighbVtx 𝑋)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ (𝑈 ∈ 𝐷 ∧ 𝑊 ∈ 𝐷) ∧ 𝑈 ≠ 𝑊) → (({𝑈, 𝐴} ∈ 𝐸 ∧ {𝑊, 𝐴} ∈ 𝐸) → 𝐴 = 𝑋))
Theorem	frgrconngr 30925	A friendship graph is connected, see remark 1 in [MertziosUnger] p. 153 (after Proposition 1): "An arbitrary friendship graph has to be connected, ... ". (Contributed by Alexander van der Vekens, 6-Dec-2017.) (Revised by AV, 1-Apr-2021.)
⊢ (𝐺 ∈ FriendGraph → 𝐺 ∈ ConnGraph)
Theorem	vdgn0frgrv2 30926	A vertex in a friendship graph with more than one vertex cannot have degree 0. (Contributed by Alexander van der Vekens, 9-Dec-2017.) (Revised by AV, 4-Apr-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ 𝑁 ∈ 𝑉) → (1 < (♯‘𝑉) → ((VtxDeg‘𝐺)‘𝑁) ≠ 0))
Theorem	vdgn1frgrv2 30927	Any vertex in a friendship graph does not have degree 1, see remark 2 in [MertziosUnger] p. 153 (after Proposition 1): "... no node v of it [a friendship graph] may have deg(v) = 1.". (Contributed by Alexander van der Vekens, 10-Dec-2017.) (Revised by AV, 4-Apr-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ 𝑁 ∈ 𝑉) → (1 < (♯‘𝑉) → ((VtxDeg‘𝐺)‘𝑁) ≠ 1))
Theorem	vdgn1frgrv3 30928*	Any vertex in a friendship graph does not have degree 1, see remark 2 in [MertziosUnger] p. 153 (after Proposition 1): "... no node v of it [a friendship graph] may have deg(v) = 1.". (Contributed by Alexander van der Vekens, 4-Sep-2018.) (Revised by AV, 4-Apr-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ 1 < (♯‘𝑉)) → ∀𝑣 ∈ 𝑉 ((VtxDeg‘𝐺)‘𝑣) ≠ 1)
Theorem	vdgfrgrgt2 30929	Any vertex in a friendship graph (with more than one vertex - then, actually, the graph must have at least three vertices, because otherwise, it would not be a friendship graph) has at least degree 2, see remark 3 in [MertziosUnger] p. 153 (after Proposition 1): "It follows that deg(v) >= 2 for every node v of a friendship graph". (Contributed by Alexander van der Vekens, 21-Dec-2017.) (Revised by AV, 5-Apr-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ 𝑁 ∈ 𝑉) → (1 < (♯‘𝑉) → 2 ≤ ((VtxDeg‘𝐺)‘𝑁)))
17.5.4  Huneke's Proof of the Friendship Theorem In this section, the friendship theorem friendship 31030 is proven by formalizing Huneke's proof, see [Huneke] pp. 1-2. The three claims (see frgrncvvdeq 30940, frgrregorufr 30956 and frrusgrord0 30971) and additional statements (numbered in the order of their occurrence in the paper) in Huneke's proof are cited in the corresponding theorems.
Theorem	frgrncvvdeqlem1 30930	Lemma 1 for frgrncvvdeq 30940. (Contributed by Alexander van der Vekens, 23-Dec-2017.) (Revised by AV, 8-May-2021.) (Proof shortened by AV, 12-Feb-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    &   ⊢ 𝐷 = (𝐺 NeighbVtx 𝑋)    &   ⊢ 𝑁 = (𝐺 NeighbVtx 𝑌)    &   ⊢ (𝜑 → 𝑋 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑌 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑋 ≠ 𝑌)    &   ⊢ (𝜑 → 𝑌 ∉ 𝐷)    &   ⊢ (𝜑 → 𝐺 ∈ FriendGraph )    &   ⊢ 𝐴 = (𝑥 ∈ 𝐷 ↦ (℩𝑦 ∈ 𝑁 {𝑥, 𝑦} ∈ 𝐸))    ⇒   ⊢ (𝜑 → 𝑋 ∉ 𝑁)
Theorem	frgrncvvdeqlem2 30931*	Lemma 2 for frgrncvvdeq 30940. In a friendship graph, for each neighbor of a vertex there is exactly one neighbor of another vertex so that there is an edge between these two neighbors. (Contributed by Alexander van der Vekens, 22-Dec-2017.) (Revised by AV, 10-May-2021.) (Proof shortened by AV, 12-Feb-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    &   ⊢ 𝐷 = (𝐺 NeighbVtx 𝑋)    &   ⊢ 𝑁 = (𝐺 NeighbVtx 𝑌)    &   ⊢ (𝜑 → 𝑋 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑌 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑋 ≠ 𝑌)    &   ⊢ (𝜑 → 𝑌 ∉ 𝐷)    &   ⊢ (𝜑 → 𝐺 ∈ FriendGraph )    &   ⊢ 𝐴 = (𝑥 ∈ 𝐷 ↦ (℩𝑦 ∈ 𝑁 {𝑥, 𝑦} ∈ 𝐸))    ⇒   ⊢ ((𝜑 ∧ 𝑥 ∈ 𝐷) → ∃!𝑦 ∈ 𝑁 {𝑥, 𝑦} ∈ 𝐸)
Theorem	frgrncvvdeqlem3 30932*	Lemma 3 for frgrncvvdeq 30940. The unique neighbor of a vertex (expressed by a restricted iota) is the intersection of the corresponding neighborhoods. (Contributed by Alexander van der Vekens, 18-Dec-2017.) (Revised by AV, 10-May-2021.) (Proof shortened by AV, 12-Feb-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    &   ⊢ 𝐷 = (𝐺 NeighbVtx 𝑋)    &   ⊢ 𝑁 = (𝐺 NeighbVtx 𝑌)    &   ⊢ (𝜑 → 𝑋 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑌 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑋 ≠ 𝑌)    &   ⊢ (𝜑 → 𝑌 ∉ 𝐷)    &   ⊢ (𝜑 → 𝐺 ∈ FriendGraph )    &   ⊢ 𝐴 = (𝑥 ∈ 𝐷 ↦ (℩𝑦 ∈ 𝑁 {𝑥, 𝑦} ∈ 𝐸))    ⇒   ⊢ ((𝜑 ∧ 𝑥 ∈ 𝐷) → {(℩𝑦 ∈ 𝑁 {𝑥, 𝑦} ∈ 𝐸)} = ((𝐺 NeighbVtx 𝑥) ∩ 𝑁))
Theorem	frgrncvvdeqlem4 30933*	Lemma 4 for frgrncvvdeq 30940. The mapping of neighbors to neighbors is a function. (Contributed by Alexander van der Vekens, 22-Dec-2017.) (Revised by AV, 10-May-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    &   ⊢ 𝐷 = (𝐺 NeighbVtx 𝑋)    &   ⊢ 𝑁 = (𝐺 NeighbVtx 𝑌)    &   ⊢ (𝜑 → 𝑋 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑌 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑋 ≠ 𝑌)    &   ⊢ (𝜑 → 𝑌 ∉ 𝐷)    &   ⊢ (𝜑 → 𝐺 ∈ FriendGraph )    &   ⊢ 𝐴 = (𝑥 ∈ 𝐷 ↦ (℩𝑦 ∈ 𝑁 {𝑥, 𝑦} ∈ 𝐸))    ⇒   ⊢ (𝜑 → 𝐴:𝐷⟶𝑁)
Theorem	frgrncvvdeqlem5 30934*	Lemma 5 for frgrncvvdeq 30940. The mapping of neighbors to neighbors applied on a vertex is the intersection of the corresponding neighborhoods. (Contributed by Alexander van der Vekens, 23-Dec-2017.) (Revised by AV, 10-May-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    &   ⊢ 𝐷 = (𝐺 NeighbVtx 𝑋)    &   ⊢ 𝑁 = (𝐺 NeighbVtx 𝑌)    &   ⊢ (𝜑 → 𝑋 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑌 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑋 ≠ 𝑌)    &   ⊢ (𝜑 → 𝑌 ∉ 𝐷)    &   ⊢ (𝜑 → 𝐺 ∈ FriendGraph )    &   ⊢ 𝐴 = (𝑥 ∈ 𝐷 ↦ (℩𝑦 ∈ 𝑁 {𝑥, 𝑦} ∈ 𝐸))    ⇒   ⊢ ((𝜑 ∧ 𝑥 ∈ 𝐷) → {(𝐴‘𝑥)} = ((𝐺 NeighbVtx 𝑥) ∩ 𝑁))
Theorem	frgrncvvdeqlem6 30935*	Lemma 6 for frgrncvvdeq 30940. (Contributed by Alexander van der Vekens, 23-Dec-2017.) (Revised by AV, 10-May-2021.) (Proof shortened by AV, 30-Dec-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    &   ⊢ 𝐷 = (𝐺 NeighbVtx 𝑋)    &   ⊢ 𝑁 = (𝐺 NeighbVtx 𝑌)    &   ⊢ (𝜑 → 𝑋 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑌 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑋 ≠ 𝑌)    &   ⊢ (𝜑 → 𝑌 ∉ 𝐷)    &   ⊢ (𝜑 → 𝐺 ∈ FriendGraph )    &   ⊢ 𝐴 = (𝑥 ∈ 𝐷 ↦ (℩𝑦 ∈ 𝑁 {𝑥, 𝑦} ∈ 𝐸))    ⇒   ⊢ ((𝜑 ∧ 𝑥 ∈ 𝐷) → {𝑥, (𝐴‘𝑥)} ∈ 𝐸)
Theorem	frgrncvvdeqlem7 30936*	Lemma 7 for frgrncvvdeq 30940. This corresponds to statement 1 in [Huneke] p. 1: "This common neighbor cannot be x, as x and y are not adjacent.". This is only an observation, which is not required to proof the friendship theorem. (Contributed by Alexander van der Vekens, 23-Dec-2017.) (Revised by AV, 10-May-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    &   ⊢ 𝐷 = (𝐺 NeighbVtx 𝑋)    &   ⊢ 𝑁 = (𝐺 NeighbVtx 𝑌)    &   ⊢ (𝜑 → 𝑋 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑌 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑋 ≠ 𝑌)    &   ⊢ (𝜑 → 𝑌 ∉ 𝐷)    &   ⊢ (𝜑 → 𝐺 ∈ FriendGraph )    &   ⊢ 𝐴 = (𝑥 ∈ 𝐷 ↦ (℩𝑦 ∈ 𝑁 {𝑥, 𝑦} ∈ 𝐸))    ⇒   ⊢ (𝜑 → ∀𝑥 ∈ 𝐷 (𝐴‘𝑥) ≠ 𝑋)
Theorem	frgrncvvdeqlem8 30937*	Lemma 8 for frgrncvvdeq 30940. This corresponds to statement 2 in [Huneke] p. 1: "The map is one-to-one since z in N(x) is uniquely determined as the common neighbor of x and a(x)". (Contributed by Alexander van der Vekens, 23-Dec-2017.) (Revised by AV, 10-May-2021.) (Revised by AV, 30-Dec-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    &   ⊢ 𝐷 = (𝐺 NeighbVtx 𝑋)    &   ⊢ 𝑁 = (𝐺 NeighbVtx 𝑌)    &   ⊢ (𝜑 → 𝑋 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑌 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑋 ≠ 𝑌)    &   ⊢ (𝜑 → 𝑌 ∉ 𝐷)    &   ⊢ (𝜑 → 𝐺 ∈ FriendGraph )    &   ⊢ 𝐴 = (𝑥 ∈ 𝐷 ↦ (℩𝑦 ∈ 𝑁 {𝑥, 𝑦} ∈ 𝐸))    ⇒   ⊢ (𝜑 → 𝐴:𝐷⟶1-1𝑁)
Theorem	frgrncvvdeqlem9 30938*	Lemma 9 for frgrncvvdeq 30940. This corresponds to statement 3 in [Huneke] p. 1: "By symmetry the map is onto". (Contributed by Alexander van der Vekens, 24-Dec-2017.) (Revised by AV, 10-May-2021.) (Proof shortened by AV, 12-Feb-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    &   ⊢ 𝐷 = (𝐺 NeighbVtx 𝑋)    &   ⊢ 𝑁 = (𝐺 NeighbVtx 𝑌)    &   ⊢ (𝜑 → 𝑋 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑌 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑋 ≠ 𝑌)    &   ⊢ (𝜑 → 𝑌 ∉ 𝐷)    &   ⊢ (𝜑 → 𝐺 ∈ FriendGraph )    &   ⊢ 𝐴 = (𝑥 ∈ 𝐷 ↦ (℩𝑦 ∈ 𝑁 {𝑥, 𝑦} ∈ 𝐸))    ⇒   ⊢ (𝜑 → 𝐴:𝐷⟶onto𝑁)
Theorem	frgrncvvdeqlem10 30939*	Lemma 10 for frgrncvvdeq 30940. (Contributed by Alexander van der Vekens, 24-Dec-2017.) (Revised by AV, 10-May-2021.) (Proof shortened by AV, 30-Dec-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    &   ⊢ 𝐷 = (𝐺 NeighbVtx 𝑋)    &   ⊢ 𝑁 = (𝐺 NeighbVtx 𝑌)    &   ⊢ (𝜑 → 𝑋 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑌 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑋 ≠ 𝑌)    &   ⊢ (𝜑 → 𝑌 ∉ 𝐷)    &   ⊢ (𝜑 → 𝐺 ∈ FriendGraph )    &   ⊢ 𝐴 = (𝑥 ∈ 𝐷 ↦ (℩𝑦 ∈ 𝑁 {𝑥, 𝑦} ∈ 𝐸))    ⇒   ⊢ (𝜑 → 𝐴:𝐷⟶1-1onto𝑁)
Theorem	frgrncvvdeq 30940*	In a friendship graph, two vertices which are not connected by an edge have the same degree. This corresponds to claim 1 in [Huneke] p. 1: "If x,y are elements of (the friendship graph) G and are not adjacent, then they have the same degree (i.e., the same number of adjacent vertices).". (Contributed by Alexander van der Vekens, 19-Dec-2017.) (Revised by AV, 10-May-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    ⇒   ⊢ (𝐺 ∈ FriendGraph → ∀𝑥 ∈ 𝑉 ∀𝑦 ∈ (𝑉 ∖ {𝑥})(𝑦 ∉ (𝐺 NeighbVtx 𝑥) → (𝐷‘𝑥) = (𝐷‘𝑦)))
Theorem	frgrwopreglem4a 30941	In a friendship graph any two vertices with different degrees are connected. Alternate version of frgrwopreglem4 30946 without a fixed degree and without using the sets 𝐴 and 𝐵. (Contributed by Alexander van der Vekens, 30-Dec-2017.) (Revised by AV, 4-Feb-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ (𝑋 ∈ 𝑉 ∧ 𝑌 ∈ 𝑉) ∧ (𝐷‘𝑋) ≠ (𝐷‘𝑌)) → {𝑋, 𝑌} ∈ 𝐸)
Theorem	frgrwopreglem5a 30942	If a friendship graph has two vertices with the same degree and two other vertices with different degrees, then there is a 4-cycle in the graph. Alternate version of frgrwopreglem5 30952 without a fixed degree and without using the sets 𝐴 and 𝐵. (Contributed by Alexander van der Vekens, 31-Dec-2017.) (Revised by AV, 4-Feb-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ ((𝐴 ∈ 𝑉 ∧ 𝑋 ∈ 𝑉) ∧ (𝐵 ∈ 𝑉 ∧ 𝑌 ∈ 𝑉)) ∧ ((𝐷‘𝐴) = (𝐷‘𝑋) ∧ (𝐷‘𝐴) ≠ (𝐷‘𝐵) ∧ (𝐷‘𝑋) ≠ (𝐷‘𝑌))) → (({𝐴, 𝐵} ∈ 𝐸 ∧ {𝐵, 𝑋} ∈ 𝐸) ∧ ({𝑋, 𝑌} ∈ 𝐸 ∧ {𝑌, 𝐴} ∈ 𝐸)))
Theorem	frgrwopreglem1 30943*	Lemma 1 for frgrwopreg 30954: the classes 𝐴 and 𝐵 are sets. The definition of 𝐴 and 𝐵 corresponds to definition 3 in [Huneke] p. 2: "Let A be the set of all vertices of degree k, let B be the set of all vertices of degree different from k, ..." (Contributed by Alexander van der Vekens, 31-Dec-2017.) (Revised by AV, 10-May-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    &   ⊢ 𝐴 = {𝑥 ∈ 𝑉 ∣ (𝐷‘𝑥) = 𝐾}    &   ⊢ 𝐵 = (𝑉 ∖ 𝐴)    ⇒   ⊢ (𝐴 ∈ V ∧ 𝐵 ∈ V)
Theorem	frgrwopreglem2 30944*	Lemma 2 for frgrwopreg 30954. If the set 𝐴 of vertices of degree 𝐾 is not empty in a friendship graph with at least two vertices, then 𝐾 must be greater than 1 . This is only an observation, which is not required for the proof the friendship theorem. (Contributed by Alexander van der Vekens, 30-Dec-2017.) (Revised by AV, 2-Jan-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    &   ⊢ 𝐴 = {𝑥 ∈ 𝑉 ∣ (𝐷‘𝑥) = 𝐾}    &   ⊢ 𝐵 = (𝑉 ∖ 𝐴)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ 1 < (♯‘𝑉) ∧ 𝐴 ≠ ∅) → 2 ≤ 𝐾)
Theorem	frgrwopreglem3 30945*	Lemma 3 for frgrwopreg 30954. The vertices in the sets 𝐴 and 𝐵 have different degrees. (Contributed by Alexander van der Vekens, 30-Dec-2017.) (Revised by AV, 10-May-2021.) (Proof shortened by AV, 2-Jan-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    &   ⊢ 𝐴 = {𝑥 ∈ 𝑉 ∣ (𝐷‘𝑥) = 𝐾}    &   ⊢ 𝐵 = (𝑉 ∖ 𝐴)    ⇒   ⊢ ((𝑋 ∈ 𝐴 ∧ 𝑌 ∈ 𝐵) → (𝐷‘𝑋) ≠ (𝐷‘𝑌))
Theorem	frgrwopreglem4 30946*	Lemma 4 for frgrwopreg 30954. In a friendship graph each vertex with degree 𝐾 is connected with any vertex with degree other than 𝐾. This corresponds to statement 4 in [Huneke] p. 2: "By the first claim, every vertex in A is adjacent to every vertex in B.". (Contributed by Alexander van der Vekens, 30-Dec-2017.) (Revised by AV, 10-May-2021.) (Proof shortened by AV, 4-Feb-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    &   ⊢ 𝐴 = {𝑥 ∈ 𝑉 ∣ (𝐷‘𝑥) = 𝐾}    &   ⊢ 𝐵 = (𝑉 ∖ 𝐴)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ (𝐺 ∈ FriendGraph → ∀𝑎 ∈ 𝐴 ∀𝑏 ∈ 𝐵 {𝑎, 𝑏} ∈ 𝐸)
Theorem	frgrwopregasn 30947*	According to statement 5 in [Huneke] p. 2: "If A ... is a singleton, then that singleton is a universal friend". This version of frgrwopreg1 30949 is stricter (claiming that the singleton itself is a universal friend instead of claiming the existence of a universal friend only) and therefore closer to Huneke's statement. This strict variant, however, is not required for the proof of the friendship theorem. (Contributed by Alexander van der Vekens, 1-Jan-2018.) (Revised by AV, 4-Feb-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    &   ⊢ 𝐴 = {𝑥 ∈ 𝑉 ∣ (𝐷‘𝑥) = 𝐾}    &   ⊢ 𝐵 = (𝑉 ∖ 𝐴)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ 𝑋 ∈ 𝑉 ∧ 𝐴 = {𝑋}) → ∀𝑤 ∈ (𝑉 ∖ {𝑋}){𝑋, 𝑤} ∈ 𝐸)
Theorem	frgrwopregbsn 30948*	According to statement 5 in [Huneke] p. 2: "If ... B is a singleton, then that singleton is a universal friend". This version of frgrwopreg2 30950 is stricter (claiming that the singleton itself is a universal friend instead of claiming the existence of a universal friend only) and therefore closer to Huneke's statement. This strict variant, however, is not required for the proof of the friendship theorem. (Contributed by AV, 4-Feb-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    &   ⊢ 𝐴 = {𝑥 ∈ 𝑉 ∣ (𝐷‘𝑥) = 𝐾}    &   ⊢ 𝐵 = (𝑉 ∖ 𝐴)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ 𝑋 ∈ 𝑉 ∧ 𝐵 = {𝑋}) → ∀𝑤 ∈ (𝑉 ∖ {𝑋}){𝑋, 𝑤} ∈ 𝐸)
Theorem	frgrwopreg1 30949*	According to statement 5 in [Huneke] p. 2: "If A ... is a singleton, then that singleton is a universal friend". (Contributed by Alexander van der Vekens, 1-Jan-2018.) (Proof shortened by AV, 4-Feb-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    &   ⊢ 𝐴 = {𝑥 ∈ 𝑉 ∣ (𝐷‘𝑥) = 𝐾}    &   ⊢ 𝐵 = (𝑉 ∖ 𝐴)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ (♯‘𝐴) = 1) → ∃𝑣 ∈ 𝑉 ∀𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ 𝐸)
Theorem	frgrwopreg2 30950*	According to statement 5 in [Huneke] p. 2: "If ... B is a singleton, then that singleton is a universal friend". (Contributed by Alexander van der Vekens, 1-Jan-2018.) (Proof shortened by AV, 4-Feb-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    &   ⊢ 𝐴 = {𝑥 ∈ 𝑉 ∣ (𝐷‘𝑥) = 𝐾}    &   ⊢ 𝐵 = (𝑉 ∖ 𝐴)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ (♯‘𝐵) = 1) → ∃𝑣 ∈ 𝑉 ∀𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ 𝐸)
Theorem	frgrwopreglem5lem 30951*	Lemma for frgrwopreglem5 30952. (Contributed by AV, 5-Feb-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    &   ⊢ 𝐴 = {𝑥 ∈ 𝑉 ∣ (𝐷‘𝑥) = 𝐾}    &   ⊢ 𝐵 = (𝑉 ∖ 𝐴)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ (((𝑎 ∈ 𝐴 ∧ 𝑥 ∈ 𝐴) ∧ (𝑏 ∈ 𝐵 ∧ 𝑦 ∈ 𝐵)) → ((𝐷‘𝑎) = (𝐷‘𝑥) ∧ (𝐷‘𝑎) ≠ (𝐷‘𝑏) ∧ (𝐷‘𝑥) ≠ (𝐷‘𝑦)))
Theorem	frgrwopreglem5 30952*	Lemma 5 for frgrwopreg 30954. If 𝐴 as well as 𝐵 contain at least two vertices, there is a 4-cycle in a friendship graph. This corresponds to statement 6 in [Huneke] p. 2: "... otherwise, there are two different vertices in A, and they have two common neighbors in B, ...". (Contributed by Alexander van der Vekens, 31-Dec-2017.) (Proof shortened by AV, 5-Feb-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    &   ⊢ 𝐴 = {𝑥 ∈ 𝑉 ∣ (𝐷‘𝑥) = 𝐾}    &   ⊢ 𝐵 = (𝑉 ∖ 𝐴)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ 1 < (♯‘𝐴) ∧ 1 < (♯‘𝐵)) → ∃𝑎 ∈ 𝐴 ∃𝑥 ∈ 𝐴 ∃𝑏 ∈ 𝐵 ∃𝑦 ∈ 𝐵 ((𝑎 ≠ 𝑥 ∧ 𝑏 ≠ 𝑦) ∧ ({𝑎, 𝑏} ∈ 𝐸 ∧ {𝑏, 𝑥} ∈ 𝐸) ∧ ({𝑥, 𝑦} ∈ 𝐸 ∧ {𝑦, 𝑎} ∈ 𝐸)))
Theorem	frgrwopreglem5ALT 30953*	Alternate direct proof of frgrwopreglem5 30952, not using frgrwopreglem5a 30942. This proof would be even a little bit shorter than the proof of frgrwopreglem5 30952 without using frgrwopreglem5lem 30951. (Contributed by Alexander van der Vekens, 31-Dec-2017.) (Revised by AV, 3-Jan-2022.) (Proof shortened by AV, 5-Feb-2022.) (New usage is discouraged.) (Proof modification is discouraged.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    &   ⊢ 𝐴 = {𝑥 ∈ 𝑉 ∣ (𝐷‘𝑥) = 𝐾}    &   ⊢ 𝐵 = (𝑉 ∖ 𝐴)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ 1 < (♯‘𝐴) ∧ 1 < (♯‘𝐵)) → ∃𝑎 ∈ 𝐴 ∃𝑥 ∈ 𝐴 ∃𝑏 ∈ 𝐵 ∃𝑦 ∈ 𝐵 ((𝑎 ≠ 𝑥 ∧ 𝑏 ≠ 𝑦) ∧ ({𝑎, 𝑏} ∈ 𝐸 ∧ {𝑏, 𝑥} ∈ 𝐸) ∧ ({𝑥, 𝑦} ∈ 𝐸 ∧ {𝑦, 𝑎} ∈ 𝐸)))
Theorem	frgrwopreg 30954*	In a friendship graph there are either no vertices (𝐴 = ∅) or exactly one vertex ((♯‘𝐴) = 1) having degree 𝐾, or all (𝐵 = ∅) or all except one vertices ((♯‘𝐵) = 1) have degree 𝐾. (Contributed by Alexander van der Vekens, 31-Dec-2017.) (Revised by AV, 10-May-2021.) (Proof shortened by AV, 3-Jan-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    &   ⊢ 𝐴 = {𝑥 ∈ 𝑉 ∣ (𝐷‘𝑥) = 𝐾}    &   ⊢ 𝐵 = (𝑉 ∖ 𝐴)    ⇒   ⊢ (𝐺 ∈ FriendGraph → (((♯‘𝐴) = 1 ∨ 𝐴 = ∅) ∨ ((♯‘𝐵) = 1 ∨ 𝐵 = ∅)))
Theorem	frgrregorufr0 30955*	In a friendship graph there are either no vertices having degree 𝐾, or all vertices have degree 𝐾 for any (nonnegative integer) 𝐾, unless there is a universal friend. This corresponds to claim 2 in [Huneke] p. 2: "... all vertices have degree k, unless there is a universal friend." (Contributed by Alexander van der Vekens, 1-Jan-2018.) (Revised by AV, 11-May-2021.) (Proof shortened by AV, 3-Jan-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    ⇒   ⊢ (𝐺 ∈ FriendGraph → (∀𝑣 ∈ 𝑉 (𝐷‘𝑣) = 𝐾 ∨ ∀𝑣 ∈ 𝑉 (𝐷‘𝑣) ≠ 𝐾 ∨ ∃𝑣 ∈ 𝑉 ∀𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ 𝐸))
Theorem	frgrregorufr 30956*	If there is a vertex having degree 𝐾 for each (nonnegative integer) 𝐾 in a friendship graph, then either all vertices have degree 𝐾 or there is a universal friend. This corresponds to claim 2 in [Huneke] p. 2: "Suppose there is a vertex of degree k > 1. ... all vertices have degree k, unless there is a universal friend. ... It follows that G is k-regular, i.e., the degree of every vertex is k". (Contributed by Alexander van der Vekens, 1-Jan-2018.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    &   ⊢ 𝐷 = (VtxDeg‘𝐺)    ⇒   ⊢ (𝐺 ∈ FriendGraph → (∃𝑎 ∈ 𝑉 (𝐷‘𝑎) = 𝐾 → (∀𝑣 ∈ 𝑉 (𝐷‘𝑣) = 𝐾 ∨ ∃𝑣 ∈ 𝑉 ∀𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ 𝐸)))
Theorem	frgrregorufrg 30957*	If there is a vertex having degree 𝑘 for each nonnegative integer 𝑘 in a friendship graph, then there is a universal friend. This corresponds to claim 2 in [Huneke] p. 2: "Suppose there is a vertex of degree k > 1. ... all vertices have degree k, unless there is a universal friend. ... It follows that G is k-regular, i.e., the degree of every vertex is k". Variant of frgrregorufr 30956 with generalization. (Contributed by Alexander van der Vekens, 6-Sep-2018.) (Revised by AV, 26-May-2021.) (Proof shortened by AV, 12-Jan-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐸 = (Edg‘𝐺)    ⇒   ⊢ (𝐺 ∈ FriendGraph → ∀𝑘 ∈ ℕ0 (∃𝑎 ∈ 𝑉 ((VtxDeg‘𝐺)‘𝑎) = 𝑘 → (𝐺 RegUSGraph 𝑘 ∨ ∃𝑣 ∈ 𝑉 ∀𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ 𝐸)))
Theorem	frgr2wwlkeu 30958*	For two different vertices in a friendship graph, there is exactly one third vertex being the middle vertex of a (simple) path/walk of length 2 between the two vertices. (Contributed by Alexander van der Vekens, 18-Feb-2018.) (Revised by AV, 12-May-2021.) (Proof shortened by AV, 4-Jan-2022.) (Revised by Ender Ting, 29-Jan-2026.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ (𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑉) ∧ 𝐴 ≠ 𝐵) → ∃!𝑐 ∈ 𝑉 ⟨“𝐴𝑐𝐵”⟩ ∈ (𝐴(2 WWalksNOn 𝐺)𝐵))
Theorem	frgr2wwlkn0 30959	In a friendship graph, there is always a path/walk of length 2 between two different vertices. (Contributed by Alexander van der Vekens, 18-Feb-2018.) (Revised by AV, 12-May-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ (𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑉) ∧ 𝐴 ≠ 𝐵) → (𝐴(2 WWalksNOn 𝐺)𝐵) ≠ ∅)
Theorem	frgr2wwlk1 30960	In a friendship graph, there is exactly one walk of length 2 between two different vertices. (Contributed by Alexander van der Vekens, 19-Feb-2018.) (Revised by AV, 13-May-2021.) (Proof shortened by AV, 16-Mar-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ (𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑉) ∧ 𝐴 ≠ 𝐵) → (♯‘(𝐴(2 WWalksNOn 𝐺)𝐵)) = 1)
Theorem	frgr2wsp1 30961	In a friendship graph, there is exactly one simple path of length 2 between two different vertices. (Contributed by Alexander van der Vekens, 3-Mar-2018.) (Revised by AV, 13-May-2021.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ (𝐴 ∈ 𝑉 ∧ 𝐵 ∈ 𝑉) ∧ 𝐴 ≠ 𝐵) → (♯‘(𝐴(2 WSPathsNOn 𝐺)𝐵)) = 1)
Theorem	frgr2wwlkeqm 30962	If there is a (simple) path of length 2 from one vertex to another vertex and a (simple) path of length 2 from the other vertex back to the first vertex in a friendship graph, then the middle vertex is the same. This is only an observation, which is not required to proof the friendship theorem. (Contributed by Alexander van der Vekens, 20-Feb-2018.) (Revised by AV, 13-May-2021.) (Proof shortened by AV, 7-Jan-2022.)
⊢ ((𝐺 ∈ FriendGraph ∧ 𝐴 ≠ 𝐵 ∧ (𝑃 ∈ 𝑋 ∧ 𝑄 ∈ 𝑌)) → ((⟨“𝐴𝑃𝐵”⟩ ∈ (𝐴(2 WWalksNOn 𝐺)𝐵) ∧ ⟨“𝐵𝑄𝐴”⟩ ∈ (𝐵(2 WWalksNOn 𝐺)𝐴)) → 𝑄 = 𝑃))
Theorem	frgrhash2wsp 30963	The number of simple paths of length 2 is n*(n-1) in a friendship graph with n vertices. This corresponds to the proof of claim 3 in [Huneke] p. 2: "... the paths of length two in G: by assumption there are ( n 2 ) such paths.". However, Huneke counts undirected paths, so obtains the result ((𝑛C2) = ((𝑛 · (𝑛 − 1)) / 2)), whereas we count directed paths, obtaining twice that number. (Contributed by Alexander van der Vekens, 6-Mar-2018.) (Revised by AV, 10-Jan-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) → (♯‘(2 WSPathsN 𝐺)) = ((♯‘𝑉) · ((♯‘𝑉) − 1)))
Theorem	fusgreg2wsplem 30964*	Lemma for fusgreg2wsp 30967 and related theorems. (Contributed by AV, 8-Jan-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝑀 = (𝑎 ∈ 𝑉 ↦ {𝑤 ∈ (2 WSPathsN 𝐺) ∣ (𝑤‘1) = 𝑎})    ⇒   ⊢ (𝑁 ∈ 𝑉 → (𝑝 ∈ (𝑀‘𝑁) ↔ (𝑝 ∈ (2 WSPathsN 𝐺) ∧ (𝑝‘1) = 𝑁)))
Theorem	fusgr2wsp2nb 30965*	The set of paths of length 2 with a given vertex in the middle for a finite simple graph is the union of all paths of length 2 from one neighbor to another neighbor of this vertex via this vertex. (Contributed by Alexander van der Vekens, 9-Mar-2018.) (Revised by AV, 17-May-2021.) (Proof shortened by AV, 16-Mar-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝑀 = (𝑎 ∈ 𝑉 ↦ {𝑤 ∈ (2 WSPathsN 𝐺) ∣ (𝑤‘1) = 𝑎})    ⇒   ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑁 ∈ 𝑉) → (𝑀‘𝑁) = ∪ 𝑥 ∈ (𝐺 NeighbVtx 𝑁)∪ 𝑦 ∈ ((𝐺 NeighbVtx 𝑁) ∖ {𝑥}){⟨“𝑥𝑁𝑦”⟩})
Theorem	fusgreghash2wspv 30966*	According to statement 7 in [Huneke] p. 2: "For each vertex v, there are exactly ( k 2 ) paths with length two having v in the middle, ..." in a finite k-regular graph. For directed simple paths of length 2 represented by length 3 strings, we have again k*(k-1) such paths, see also comment of frgrhash2wsp 30963. (Contributed by Alexander van der Vekens, 10-Mar-2018.) (Revised by AV, 17-May-2021.) (Proof shortened by AV, 12-Feb-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝑀 = (𝑎 ∈ 𝑉 ↦ {𝑤 ∈ (2 WSPathsN 𝐺) ∣ (𝑤‘1) = 𝑎})    ⇒   ⊢ (𝐺 ∈ FinUSGraph → ∀𝑣 ∈ 𝑉 (((VtxDeg‘𝐺)‘𝑣) = 𝐾 → (♯‘(𝑀‘𝑣)) = (𝐾 · (𝐾 − 1))))
Theorem	fusgreg2wsp 30967*	In a finite simple graph, the set of all paths of length 2 is the union of all the paths of length 2 over the vertices which are in the middle of such a path. (Contributed by Alexander van der Vekens, 10-Mar-2018.) (Revised by AV, 18-May-2021.) (Proof shortened by AV, 10-Jan-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝑀 = (𝑎 ∈ 𝑉 ↦ {𝑤 ∈ (2 WSPathsN 𝐺) ∣ (𝑤‘1) = 𝑎})    ⇒   ⊢ (𝐺 ∈ FinUSGraph → (2 WSPathsN 𝐺) = ∪ 𝑥 ∈ 𝑉 (𝑀‘𝑥))
Theorem	2wspmdisj 30968*	The sets of paths of length 2 with a given vertex in the middle are distinct for different vertices in the middle. (Contributed by Alexander van der Vekens, 11-Mar-2018.) (Revised by AV, 18-May-2021.) (Proof shortened by AV, 10-Jan-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝑀 = (𝑎 ∈ 𝑉 ↦ {𝑤 ∈ (2 WSPathsN 𝐺) ∣ (𝑤‘1) = 𝑎})    ⇒   ⊢ Disj 𝑥 ∈ 𝑉 (𝑀‘𝑥)
Theorem	fusgreghash2wsp 30969*	In a finite k-regular graph with N vertices there are N times "k choose 2" paths with length 2, according to statement 8 in [Huneke] p. 2: "... giving n * ( k 2 ) total paths of length two.", if the direction of traversing the path is not respected. For simple paths of length 2 represented by length 3 strings, however, we have again n*k*(k-1) such paths. (Contributed by Alexander van der Vekens, 11-Mar-2018.) (Revised by AV, 19-May-2021.) (Proof shortened by AV, 12-Jan-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑉 ≠ ∅) → (∀𝑣 ∈ 𝑉 ((VtxDeg‘𝐺)‘𝑣) = 𝐾 → (♯‘(2 WSPathsN 𝐺)) = ((♯‘𝑉) · (𝐾 · (𝐾 − 1)))))
Theorem	frrusgrord0lem 30970*	Lemma for frrusgrord0 30971. (Contributed by AV, 12-Jan-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅) ∧ ∀𝑣 ∈ 𝑉 ((VtxDeg‘𝐺)‘𝑣) = 𝐾) → (𝐾 ∈ ℂ ∧ (♯‘𝑉) ∈ ℂ ∧ (♯‘𝑉) ≠ 0))
Theorem	frrusgrord0 30971*	If a nonempty finite friendship graph is k-regular, its order is k(k-1)+1. This corresponds to claim 3 in [Huneke] p. 2: "Next we claim that the number n of vertices in G is exactly k(k-1)+1.". (Contributed by Alexander van der Vekens, 11-Mar-2018.) (Revised by AV, 26-May-2021.) (Proof shortened by AV, 12-Jan-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅) → (∀𝑣 ∈ 𝑉 ((VtxDeg‘𝐺)‘𝑣) = 𝐾 → (♯‘𝑉) = ((𝐾 · (𝐾 − 1)) + 1)))
Theorem	frrusgrord 30972	If a nonempty finite friendship graph is k-regular, its order is k(k-1)+1. This corresponds to claim 3 in [Huneke] p. 2: "Next we claim that the number n of vertices in G is exactly k(k-1)+1.". Variant of frrusgrord0 30971, using the definition RegUSGraph (df-rusgr 30169). (Contributed by Alexander van der Vekens, 25-Aug-2018.) (Revised by AV, 26-May-2021.) (Proof shortened by AV, 12-Jan-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ ((𝑉 ∈ Fin ∧ 𝑉 ≠ ∅) → ((𝐺 ∈ FriendGraph ∧ 𝐺 RegUSGraph 𝐾) → (♯‘𝑉) = ((𝐾 · (𝐾 − 1)) + 1)))
Theorem	numclwwlk2lem1lem 30973	Lemma for numclwwlk2lem1 31007. (Contributed by Alexander van der Vekens, 3-Oct-2018.) (Revised by AV, 27-May-2021.) (Revised by AV, 15-Mar-2022.)
⊢ ((𝑋 ∈ (Vtx‘𝐺) ∧ 𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (lastS‘𝑊) ≠ (𝑊‘0)) → (((𝑊 ++ ⟨“𝑋”⟩)‘0) = (𝑊‘0) ∧ ((𝑊 ++ ⟨“𝑋”⟩)‘𝑁) ≠ (𝑊‘0)))
Theorem	2clwwlklem 30974	Lemma for clwwnonrepclwwnon 30976 and extwwlkfab 30983. (Contributed by Alexander van der Vekens, 18-Sep-2018.) (Revised by AV, 10-May-2022.) (Revised by AV, 30-Oct-2022.)
⊢ ((𝑊 ∈ (𝑁 ClWWalksN 𝐺) ∧ 𝑁 ∈ (ℤ≥‘3)) → ((𝑊 prefix (𝑁 − 2))‘0) = (𝑊‘0))
Theorem	clwwnrepclwwn 30975	If the initial vertex of a closed walk occurs another time in the walk, the walk starts with a closed walk. Notice that 3 ≤ 𝑁 is required, because for 𝑁 = 2, (𝑤 prefix (𝑁 − 2)) = (𝑤 prefix 0) = ∅, but ∅ (and anything else) is not a representation of an empty closed walk as word, see clwwlkn0 30649. (Contributed by Alexander van der Vekens, 15-Sep-2018.) (Revised by AV, 28-May-2021.) (Revised by AV, 30-Oct-2022.)
⊢ ((𝑁 ∈ (ℤ≥‘3) ∧ 𝑊 ∈ (𝑁 ClWWalksN 𝐺) ∧ (𝑊‘(𝑁 − 2)) = (𝑊‘0)) → (𝑊 prefix (𝑁 − 2)) ∈ ((𝑁 − 2) ClWWalksN 𝐺))
Theorem	clwwnonrepclwwnon 30976	If the initial vertex of a closed walk occurs another time in the walk, the walk starts with a closed walk on this vertex. See also the remarks in clwwnrepclwwn 30975. (Contributed by AV, 24-Apr-2022.) (Revised by AV, 10-May-2022.) (Revised by AV, 30-Oct-2022.)
⊢ ((𝑁 ∈ (ℤ≥‘3) ∧ 𝑊 ∈ (𝑋(ClWWalksNOn‘𝐺)𝑁) ∧ (𝑊‘(𝑁 − 2)) = 𝑋) → (𝑊 prefix (𝑁 − 2)) ∈ (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2)))
Theorem	2clwwlk2clwwlklem 30977	Lemma for 2clwwlk2clwwlk 30981. (Contributed by AV, 27-Apr-2022.)
⊢ ((𝑁 ∈ (ℤ≥‘3) ∧ 𝑊 ∈ (𝑋(ClWWalksNOn‘𝐺)𝑁) ∧ (𝑊‘(𝑁 − 2)) = (𝑊‘0)) → (𝑊 substr ⟨(𝑁 − 2), 𝑁⟩) ∈ (𝑋(ClWWalksNOn‘𝐺)2))
Theorem	2clwwlk 30978*	Value of operation 𝐶, mapping a vertex v and an integer n greater than 1 to the "closed n-walks v(0) ... v(n-2) v(n-1) v(n) from v = v(0) = v(n) with v(n-2) = v" according to definition 6 in [Huneke] p. 2. Such closed walks are "double loops" consisting of a closed (n-2)-walk v = v(0) ... v(n-2) = v and a closed 2-walk v = v(n-2) v(n-1) v(n) = v, see 2clwwlk2clwwlk 30981. (𝑋𝐶𝑁) is called the "set of double loops of length 𝑁 on vertex 𝑋 " in the following. (Contributed by Alexander van der Vekens, 14-Sep-2018.) (Revised by AV, 29-May-2021.) (Revised by AV, 20-Apr-2022.)
⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})    ⇒   ⊢ ((𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘2)) → (𝑋𝐶𝑁) = {𝑤 ∈ (𝑋(ClWWalksNOn‘𝐺)𝑁) ∣ (𝑤‘(𝑁 − 2)) = 𝑋})
Theorem	2clwwlk2 30979*	The set (𝑋𝐶2) of double loops of length 2 on a vertex 𝑋 is equal to the set of closed walks with length 2 on 𝑋. Considered as "double loops", the first of the two closed walks/loops is degenerated, i.e., has length 0. (Contributed by AV, 18-Feb-2022.) (Revised by AV, 20-Apr-2022.)
⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})    ⇒   ⊢ (𝑋 ∈ 𝑉 → (𝑋𝐶2) = (𝑋(ClWWalksNOn‘𝐺)2))
Theorem	2clwwlkel 30980*	Characterization of an element of the value of operation 𝐶, i.e., of a word being a double loop of length 𝑁 on vertex 𝑋. (Contributed by Alexander van der Vekens, 24-Sep-2018.) (Revised by AV, 29-May-2021.) (Revised by AV, 20-Apr-2022.)
⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})    ⇒   ⊢ ((𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘2)) → (𝑊 ∈ (𝑋𝐶𝑁) ↔ (𝑊 ∈ (𝑋(ClWWalksNOn‘𝐺)𝑁) ∧ (𝑊‘(𝑁 − 2)) = 𝑋)))
Theorem	2clwwlk2clwwlk 30981*	An element of the value of operation 𝐶, i.e., a word being a double loop of length 𝑁 on vertex 𝑋, is composed of two closed walks. (Contributed by AV, 28-Apr-2022.) (Proof shortened by AV, 3-Nov-2022.)
⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})    ⇒   ⊢ ((𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3)) → (𝑊 ∈ (𝑋𝐶𝑁) ↔ ∃𝑎 ∈ (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2))∃𝑏 ∈ (𝑋(ClWWalksNOn‘𝐺)2)𝑊 = (𝑎 ++ 𝑏)))
Theorem	numclwwlk1lem2foalem 30982	Lemma for numclwwlk1lem2foa 30985. (Contributed by AV, 29-May-2021.) (Revised by AV, 1-Nov-2022.)
⊢ (((𝑊 ∈ Word 𝑉 ∧ (♯‘𝑊) = (𝑁 − 2)) ∧ (𝑋 ∈ 𝑉 ∧ 𝑌 ∈ 𝑉) ∧ 𝑁 ∈ (ℤ≥‘3)) → ((((𝑊 ++ ⟨“𝑋”⟩) ++ ⟨“𝑌”⟩) prefix (𝑁 − 2)) = 𝑊 ∧ (((𝑊 ++ ⟨“𝑋”⟩) ++ ⟨“𝑌”⟩)‘(𝑁 − 1)) = 𝑌 ∧ (((𝑊 ++ ⟨“𝑋”⟩) ++ ⟨“𝑌”⟩)‘(𝑁 − 2)) = 𝑋))
Theorem	extwwlkfab 30983*	The set (𝑋𝐶𝑁) of double loops of length 𝑁 on vertex 𝑋 can be constructed from the set 𝐹 of closed walks on 𝑋 with length smaller by 2 than the fixed length by appending a neighbor of the last vertex and afterwards the last vertex (which is the first vertex) itself ("walking forth and back" from the last vertex). 3 ≤ 𝑁 is required since for 𝑁 = 2: 𝐹 = (𝑋(ClWWalksNOn‘𝐺)0) = ∅ (see clwwlk0on0 30713 stating that a closed walk of length 0 is not represented as word), which would result in an empty set on the right hand side, but (𝑋𝐶𝑁) need not be empty, see 2clwwlk2 30979. (Contributed by Alexander van der Vekens, 18-Sep-2018.) (Revised by AV, 29-May-2021.) (Revised by AV, 31-Oct-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})    &   ⊢ 𝐹 = (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2))    ⇒   ⊢ ((𝐺 ∈ USGraph ∧ 𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3)) → (𝑋𝐶𝑁) = {𝑤 ∈ (𝑁 ClWWalksN 𝐺) ∣ ((𝑤 prefix (𝑁 − 2)) ∈ 𝐹 ∧ (𝑤‘(𝑁 − 1)) ∈ (𝐺 NeighbVtx 𝑋) ∧ (𝑤‘(𝑁 − 2)) = 𝑋)})
Theorem	extwwlkfabel 30984*	Characterization of an element of the set (𝑋𝐶𝑁), i.e., a double loop of length 𝑁 on vertex 𝑋 with a construction from the set 𝐹 of closed walks on 𝑋 with length smaller by 2 than the fixed length by appending a neighbor of the last vertex and afterwards the last vertex (which is the first vertex) itself ("walking forth and back" from the last vertex). (Contributed by AV, 22-Feb-2022.) (Revised by AV, 31-Oct-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})    &   ⊢ 𝐹 = (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2))    ⇒   ⊢ ((𝐺 ∈ USGraph ∧ 𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3)) → (𝑊 ∈ (𝑋𝐶𝑁) ↔ (𝑊 ∈ (𝑁 ClWWalksN 𝐺) ∧ ((𝑊 prefix (𝑁 − 2)) ∈ 𝐹 ∧ (𝑊‘(𝑁 − 1)) ∈ (𝐺 NeighbVtx 𝑋) ∧ (𝑊‘(𝑁 − 2)) = 𝑋))))
Theorem	numclwwlk1lem2foa 30985*	Going forth and back from the end of a (closed) walk: 𝑊 represents the closed walk p0, ..., p(n-2), p0 = p(n-2). With 𝑋 = p(n-2) = p0 and 𝑌 = p(n-1), ((𝑊 ++ ⟨“𝑋”⟩) ++ ⟨“𝑌”⟩) represents the closed walk p0, ..., p(n-2), p(n-1), pn = p0 which is a double loop of length 𝑁 on vertex 𝑋. (Contributed by Alexander van der Vekens, 22-Sep-2018.) (Revised by AV, 29-May-2021.) (Revised by AV, 5-Mar-2022.) (Proof shortened by AV, 2-Nov-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})    &   ⊢ 𝐹 = (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2))    ⇒   ⊢ ((𝐺 ∈ USGraph ∧ 𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3)) → ((𝑊 ∈ 𝐹 ∧ 𝑌 ∈ (𝐺 NeighbVtx 𝑋)) → ((𝑊 ++ ⟨“𝑋”⟩) ++ ⟨“𝑌”⟩) ∈ (𝑋𝐶𝑁)))
Theorem	numclwwlk1lem2f 30986*	𝑇 is a function, mapping a double loop of length 𝑁 on vertex 𝑋 to the ordered pair of the first loop and the successor of 𝑋 in the second loop, which must be a neighbor of 𝑋. (Contributed by Alexander van der Vekens, 19-Sep-2018.) (Revised by AV, 29-May-2021.) (Proof shortened by AV, 23-Feb-2022.) (Revised by AV, 31-Oct-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})    &   ⊢ 𝐹 = (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2))    &   ⊢ 𝑇 = (𝑢 ∈ (𝑋𝐶𝑁) ↦ ⟨(𝑢 prefix (𝑁 − 2)), (𝑢‘(𝑁 − 1))⟩)    ⇒   ⊢ ((𝐺 ∈ USGraph ∧ 𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3)) → 𝑇:(𝑋𝐶𝑁)⟶(𝐹 × (𝐺 NeighbVtx 𝑋)))
Theorem	numclwwlk1lem2fv 30987*	Value of the function 𝑇. (Contributed by Alexander van der Vekens, 20-Sep-2018.) (Revised by AV, 29-May-2021.) (Revised by AV, 31-Oct-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})    &   ⊢ 𝐹 = (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2))    &   ⊢ 𝑇 = (𝑢 ∈ (𝑋𝐶𝑁) ↦ ⟨(𝑢 prefix (𝑁 − 2)), (𝑢‘(𝑁 − 1))⟩)    ⇒   ⊢ (𝑊 ∈ (𝑋𝐶𝑁) → (𝑇‘𝑊) = ⟨(𝑊 prefix (𝑁 − 2)), (𝑊‘(𝑁 − 1))⟩)
Theorem	numclwwlk1lem2f1 30988*	𝑇 is a 1-1 function. (Contributed by AV, 26-Sep-2018.) (Revised by AV, 29-May-2021.) (Proof shortened by AV, 23-Feb-2022.) (Revised by AV, 31-Oct-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})    &   ⊢ 𝐹 = (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2))    &   ⊢ 𝑇 = (𝑢 ∈ (𝑋𝐶𝑁) ↦ ⟨(𝑢 prefix (𝑁 − 2)), (𝑢‘(𝑁 − 1))⟩)    ⇒   ⊢ ((𝐺 ∈ USGraph ∧ 𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3)) → 𝑇:(𝑋𝐶𝑁)⟶1-1(𝐹 × (𝐺 NeighbVtx 𝑋)))
Theorem	numclwwlk1lem2fo 30989*	𝑇 is an onto function. (Contributed by Alexander van der Vekens, 20-Sep-2018.) (Revised by AV, 29-May-2021.) (Proof shortened by AV, 13-Feb-2022.) (Revised by AV, 31-Oct-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})    &   ⊢ 𝐹 = (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2))    &   ⊢ 𝑇 = (𝑢 ∈ (𝑋𝐶𝑁) ↦ ⟨(𝑢 prefix (𝑁 − 2)), (𝑢‘(𝑁 − 1))⟩)    ⇒   ⊢ ((𝐺 ∈ USGraph ∧ 𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3)) → 𝑇:(𝑋𝐶𝑁)⟶onto(𝐹 × (𝐺 NeighbVtx 𝑋)))
Theorem	numclwwlk1lem2f1o 30990*	𝑇 is a 1-1 onto function. (Contributed by Alexander van der Vekens, 26-Sep-2018.) (Revised by AV, 29-May-2021.) (Revised by AV, 6-Mar-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})    &   ⊢ 𝐹 = (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2))    &   ⊢ 𝑇 = (𝑢 ∈ (𝑋𝐶𝑁) ↦ ⟨(𝑢 prefix (𝑁 − 2)), (𝑢‘(𝑁 − 1))⟩)    ⇒   ⊢ ((𝐺 ∈ USGraph ∧ 𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3)) → 𝑇:(𝑋𝐶𝑁)⟶1-1onto(𝐹 × (𝐺 NeighbVtx 𝑋)))
Theorem	numclwwlk1lem2 30991*	The set of double loops of length 𝑁 on vertex 𝑋 and the set of closed walks of length less by 2 on 𝑋 combined with the neighbors of 𝑋 are equinumerous. (Contributed by Alexander van der Vekens, 6-Jul-2018.) (Revised by AV, 29-May-2021.) (Revised by AV, 31-Jul-2022.) (Proof shortened by AV, 3-Nov-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})    &   ⊢ 𝐹 = (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2))    ⇒   ⊢ ((𝐺 ∈ USGraph ∧ 𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3)) → (𝑋𝐶𝑁) ≈ (𝐹 × (𝐺 NeighbVtx 𝑋)))
Theorem	numclwwlk1 30992*	Statement 9 in [Huneke] p. 2: "If n > 1, then the number of closed n-walks v(0) ... v(n-2) v(n-1) v(n) from v = v(0) = v(n) with v(n-2) = v is kf(n-2)". Since 𝐺 is k-regular, the vertex v(n-2) = v has k neighbors v(n-1), so there are k walks from v(n-2) = v to v(n) = v (via each of v's neighbors) completing each of the f(n-2) walks from v=v(0) to v(n-2)=v. This theorem holds even for k=0, but not for n=2, since 𝐹 = ∅, but (𝑋𝐶2), the set of closed walks with length 2 on 𝑋, see 2clwwlk2 30979, need not be ∅ in this case. This is because of the special definition of 𝐹 and the usage of words to represent (closed) walks, and does not contradict Huneke's statement, which would read "the number of closed 2-walks v(0) v(1) v(2) from v = v(0) = v(2) ... is kf(0)", where f(0)=1 is the number of empty closed walks on v, see numclwlk1lem1 31000. If the general representation of (closed) walk is used, Huneke's statement can be proven even for n = 2, see numclwlk1 31002. This case, however, is not required to prove the friendship theorem. (Contributed by Alexander van der Vekens, 26-Sep-2018.) (Revised by AV, 29-May-2021.) (Revised by AV, 6-Mar-2022.) (Proof shortened by AV, 31-Jul-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})    &   ⊢ 𝐹 = (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2))    ⇒   ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → (♯‘(𝑋𝐶𝑁)) = (𝐾 · (♯‘𝐹)))
Theorem	clwwlknonclwlknonf1o 30993*	𝐹 is a bijection between the two representations of closed walks of a fixed positive length on a fixed vertex. (Contributed by AV, 26-May-2022.) (Proof shortened by AV, 7-Aug-2022.) (Revised by AV, 1-Nov-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝑊 = {𝑤 ∈ (ClWalks‘𝐺) ∣ ((♯‘(1st ‘𝑤)) = 𝑁 ∧ ((2nd ‘𝑤)‘0) = 𝑋)}    &   ⊢ 𝐹 = (𝑐 ∈ 𝑊 ↦ ((2nd ‘𝑐) prefix (♯‘(1st ‘𝑐))))    ⇒   ⊢ ((𝐺 ∈ USPGraph ∧ 𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ) → 𝐹:𝑊⟶1-1onto(𝑋(ClWWalksNOn‘𝐺)𝑁))
Theorem	clwwlknonclwlknonen 30994*	The sets of the two representations of closed walks of a fixed positive length on a fixed vertex are equinumerous. (Contributed by AV, 27-May-2022.) (Proof shortened by AV, 3-Nov-2022.)
⊢ ((𝐺 ∈ USPGraph ∧ 𝑋 ∈ (Vtx‘𝐺) ∧ 𝑁 ∈ ℕ) → {𝑤 ∈ (ClWalks‘𝐺) ∣ ((♯‘(1st ‘𝑤)) = 𝑁 ∧ ((2nd ‘𝑤)‘0) = 𝑋)} ≈ (𝑋(ClWWalksNOn‘𝐺)𝑁))
Theorem	dlwwlknondlwlknonf1olem1 30995	Lemma 1 for dlwwlknondlwlknonf1o 30996. (Contributed by AV, 29-May-2022.) (Revised by AV, 1-Nov-2022.)
⊢ (((♯‘(1st ‘𝑐)) = 𝑁 ∧ 𝑐 ∈ (ClWalks‘𝐺) ∧ 𝑁 ∈ (ℤ≥‘2)) → (((2nd ‘𝑐) prefix (♯‘(1st ‘𝑐)))‘(𝑁 − 2)) = ((2nd ‘𝑐)‘(𝑁 − 2)))
Theorem	dlwwlknondlwlknonf1o 30996*	𝐹 is a bijection between the two representations of double loops of a fixed positive length on a fixed vertex. (Contributed by AV, 30-May-2022.) (Revised by AV, 1-Nov-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝑊 = {𝑤 ∈ (ClWalks‘𝐺) ∣ ((♯‘(1st ‘𝑤)) = 𝑁 ∧ ((2nd ‘𝑤)‘0) = 𝑋 ∧ ((2nd ‘𝑤)‘(𝑁 − 2)) = 𝑋)}    &   ⊢ 𝐷 = {𝑤 ∈ (𝑋(ClWWalksNOn‘𝐺)𝑁) ∣ (𝑤‘(𝑁 − 2)) = 𝑋}    &   ⊢ 𝐹 = (𝑐 ∈ 𝑊 ↦ ((2nd ‘𝑐) prefix (♯‘(1st ‘𝑐))))    ⇒   ⊢ ((𝐺 ∈ USPGraph ∧ 𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘2)) → 𝐹:𝑊⟶1-1onto𝐷)
Theorem	dlwwlknondlwlknonen 30997*	The sets of the two representations of double loops of a fixed length on a fixed vertex are equinumerous. (Contributed by AV, 30-May-2022.) (Proof shortened by AV, 3-Nov-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝑊 = {𝑤 ∈ (ClWalks‘𝐺) ∣ ((♯‘(1st ‘𝑤)) = 𝑁 ∧ ((2nd ‘𝑤)‘0) = 𝑋 ∧ ((2nd ‘𝑤)‘(𝑁 − 2)) = 𝑋)}    &   ⊢ 𝐷 = {𝑤 ∈ (𝑋(ClWWalksNOn‘𝐺)𝑁) ∣ (𝑤‘(𝑁 − 2)) = 𝑋}    ⇒   ⊢ ((𝐺 ∈ USPGraph ∧ 𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘2)) → 𝑊 ≈ 𝐷)
Theorem	wlkl0 30998*	There is exactly one walk of length 0 on each vertex 𝑋. (Contributed by AV, 4-Jun-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ (𝑋 ∈ 𝑉 → {𝑤 ∈ (ClWalks‘𝐺) ∣ ((♯‘(1st ‘𝑤)) = 0 ∧ ((2nd ‘𝑤)‘0) = 𝑋)} = {⟨∅, {⟨0, 𝑋⟩}⟩})
Theorem	clwlknon2num 30999*	There are k walks of length 2 on each vertex 𝑋 in a k-regular simple graph. Variant of clwwlknon2num 30726, using the general definition of walks instead of walks as words. (Contributed by AV, 4-Jun-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    ⇒   ⊢ ((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾 ∧ 𝑋 ∈ 𝑉) → (♯‘{𝑤 ∈ (ClWalks‘𝐺) ∣ ((♯‘(1st ‘𝑤)) = 2 ∧ ((2nd ‘𝑤)‘0) = 𝑋)}) = 𝐾)
Theorem	numclwlk1lem1 31000*	Lemma 1 for numclwlk1 31002 (Statement 9 in [Huneke] p. 2 for n=2): "the number of closed 2-walks v(0) v(1) v(2) from v = v(0) = v(2) ... is kf(0)". (Contributed by AV, 23-May-2022.)
⊢ 𝑉 = (Vtx‘𝐺)    &   ⊢ 𝐶 = {𝑤 ∈ (ClWalks‘𝐺) ∣ ((♯‘(1st ‘𝑤)) = 𝑁 ∧ ((2nd ‘𝑤)‘0) = 𝑋 ∧ ((2nd ‘𝑤)‘(𝑁 − 2)) = 𝑋)}    &   ⊢ 𝐹 = {𝑤 ∈ (ClWalks‘𝐺) ∣ ((♯‘(1st ‘𝑤)) = (𝑁 − 2) ∧ ((2nd ‘𝑤)‘0) = 𝑋)}    ⇒   ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 = 2)) → (♯‘𝐶) = (𝐾 · (♯‘𝐹)))