triangle_free_edges_share_endpoint
If a simple graph H with at least one edge is triangle-free and every pair of edges shares at least one vertex, then all edges of H share a common endpoint.
Statement
theorem triangle_free_edges_share_endpoint {V : Type*} (H : SimpleGraph V) (he : ∃ a b : V, H.Adj a b) (htri : H.CliqueFree 3) (hpair : ∀ u v x y : V, H.Adj u v → H.Adj x y → u = x ∨ u = y ∨ v = x ∨ v = y) : ∃ c : V, ∀ u v : V, H.Adj u v → u = c ∨ v = c
- Source
- arXiv:2611.07924, Section 6, Theorem 6.1 proof
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For any type V and any simple graph H on V, if:
1. H has at least one edge (there exist a, b : V such that H.Adj a b),
2. H is triangle-free (H.CliqueFree 3), and
3. every pair of edges shares at least one endpoint (for all vertices u, v, x, y : V, if H.Adj u v and H.Adj x y, then u = x ∨ u = y ∨ v = x ∨ v = y),
then all edges of H are incident to a single common vertex (there exists c : V such that for all u, v : V, if H.Adj u v, then u = c ∨ v = c).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Proof sketch: The argument first establishes an auxiliary contradiction lemma showing that any three pairwise adjacent and distinct vertices form a triangle (a 3-clique), contradicting triangle-freeness. Fixing an arbitrary edge ab, if every edge in the graph contains a, then a is the desired common endpoint. Otherwise, there exists an edge pq disjoint from a, which must share vertex b with ab because all pairs of edges intersect. Finally, vertex b must be shared by all edges: any hypothetical edge uv avoiding b would have to contain a, and intersecting uv with pq then forces a triangle on vertices a, b, and a third vertex, which is impossible.
Any three pairwise distinct, pairwise adjacent vertices in H form a 3-clique, yielding a contradiction.
Assuming classical logic, we establish the helper lemma tri_contra: if x, y, z are mutually adjacent and pairwise distinct (x ≠ y, x ≠ z, y ≠ z), they form a 3-clique. Applying the hypothesis htri (that H has no 3-clique) to the finset {x, y, z} requires showing it is an n-clique of size 3 (SimpleGraph.isNClique_iff). By SimpleGraph.isClique_iff, this means showing {x, y, z} is pairwise adjacent (Set.Pairwise), which simp verifies using the edge hypotheses and symmetry of adjacency (H.adj_comm). Distinctness of the three vertices confirms the cardinality is 3.
uses
SimpleGraph.isNClique_iff,SimpleGraph.isClique_iff,Set.Pairwise,H.adj_commclassical have tri_contra : ∀ {x y z : V}, H.Adj x y → H.Adj y z → H.Adj x z → x ≠ y → x ≠ z → y ≠ z → False := by intro x y z hxy hyz hxz hne1 hne2 hne3 apply htri ({x, y, z} : Finset V) rw [SimpleGraph.isNClique_iff] constructor · rw [SimpleGraph.isClique_iff] simp [Set.Pairwise, hxy, hyz, hxz, H.adj_comm] · simp [hne1, hne2, hne3]
Fix an edge ab; if every edge contains a, then a is the desired common endpoint.
From the assumption he that H has an edge, pick an edge ab with endpoints a, b. We split into cases on whether every edge uv in H contains vertex a. If so, a is the witness c to the existential claim.
obtain ⟨a, b, hab⟩ := he by_cases halla : ∀ u v : V, H.Adj u v → u = a ∨ v = a · exact ⟨a, halla⟩
If a is not on every edge, there is an edge pq avoiding a, and one of its endpoints must be b.
Supposing not all edges contain a, there exists an edge pq with p ≠ a and q ≠ a. By hpair, the edges pq and ab must share at least one vertex, giving p = a ∨ p = b ∨ q = a ∨ q = b. Since p ≠ a and q ≠ a, the first and third cases are absurd, leaving p = b ∨ q = b (using Or.inl and Or.inr).
uses
Or.inl,Or.inr· push Not at halla obtain ⟨p, q, hpq, hpa, hqa⟩ := halla have hpbq : p = b ∨ q = b := by rcases hpair p q a b hpq hab with h | h | h | h · exact absurd h hpa · exact Or.inl h · exact absurd h hqa · exact Or.inr h
To show that b is the common endpoint, any edge uv avoiding b must contain a.
We propose b as the common endpoint for all edges. For contradiction, assume there is an edge uv with u ≠ b and v ≠ b. By hpair, uv and ab must intersect, yielding u = a ∨ u = b ∨ v = a ∨ v = b. Because u ≠ b and v ≠ b, the second and fourth possibilities are ruled out, leaving u = a ∨ v = a (using Or.inl and Or.inr).
uses
Or.inl,Or.inrrefine ⟨b, ?_⟩ intro u v huv by_contra hcon push Not at hcon obtain ⟨hub, hvb⟩ := hcon have hua_or_hva : u = a ∨ v = a := by rcases hpair u v a b huv hab with h | h | h | h · exact Or.inl h · exact absurd h hub · exact Or.inr h · exact absurd h hvb
If p = b, the edges ab, pq, and uv force a triangle on vertices a, b, q, giving a contradiction.
Assuming p = b, we inspect the two possibilities for uv: - If u = a, edges pq and uv must intersect (hpair). The cases p = u (giving a = b), p = v (giving v = b), and q = u (giving q = a) all contradict previous facts, leaving q = v. Then the edges are ab, bq, and aq. Since a, b, q are pairwise distinct, tri_contra yields a contradiction. - If v = a, intersecting pq and uv similarly forces q = u (the other cases contradict u ≠ b, a = b, or q = a). The edges ab, bq, and qa form a triangle on distinct vertices a, b, q, again contradicting tri_contra.
rcases hpbq with hpb | hqb · rcases hua_or_hva with hua | hva · have hqv : q = v := by rcases hpair p q u v hpq huv with h | h | h | h · exact absurd (by rw [← hua, ← h, hpb] : a = b) hab.ne · exact absurd (by rw [← h, hpb] : v = b) hvb · exact absurd (by rw [h, hua] : q = a) hqa · exact h rw [hpb] at hpq rw [hua, hqv.symm] at huv exact tri_contra hab hpq huv hab.ne hqa.symm hpq.ne · have hqu : q = u := by rcases hpair p q u v hpq huv with h | h | h | h · exact absurd (by rw [← h, hpb] : u = b) hub · exact absurd (by rw [← hva, ← h, hpb] : a = b) hab.ne · exact h · exact absurd (by rw [h, hva] : q = a) hqa rw [hpb] at hpq rw [hva, hqu.symm] at huv exact tri_contra hab hpq huv.symm hab.ne hqa.symm hpq.ne
If q = b, the edges ab, pq, and uv force a triangle on vertices a, b, p, giving a contradiction.
Assuming q = b, we inspect the two possibilities for uv: - If u = a, the intersection of pq and uv forces p = v (the other cases contradict p ≠ a, a = b, or v = b). The edges ab, pb, and ap form a triangle on distinct vertices a, b, p, contradicting tri_contra. - If v = a, the intersection of pq and uv forces p = u (the other cases contradict p ≠ a, u ≠ b, or a = b). The edges ab, pb, and pa form a triangle on distinct vertices a, b, p, contradicting tri_contra. This eliminates all alternatives, proving that every edge must contain b.
· rcases hua_or_hva with hua | hva · have hpv : p = v := by rcases hpair p q u v hpq huv with h | h | h | h · exact absurd (by rw [h, hua] : p = a) hpa · exact h · exact absurd (by rw [← hua, ← h, hqb] : a = b) hab.ne · exact absurd (by rw [← h, hqb] : v = b) hvb rw [hqb] at hpq rw [hua, hpv.symm] at huv exact tri_contra hab hpq.symm huv hab.ne hpa.symm hpq.ne.symm · have hpu : p = u := by rcases hpair p q u v hpq huv with h | h | h | h · exact h · exact absurd (by rw [← hva, h] : p = a) hpa · exact absurd (by rw [← h, hqb] : u = b) hub · exact absurd (by rw [← hva, ← h, hqb] : a = b) hab.ne rw [hqb] at hpq rw [hva, hpu.symm] at huv exact tri_contra hab hpq.symm huv.symm hab.ne hpa.symm hpq.ne.symm
SimpleGraph.isNClique_iff- A finite set of vertices is an n-clique in a graph if and only if it is a clique and has cardinality n.
SimpleGraph.isClique_iff- A set of vertices in a graph is a clique if and only if its elements are pairwise adjacent.
Set.Pairwise- A relation holds pairwise on a set if it holds for every pair of distinct elements in the set.
H.adj_comm- Adjacency in a simple graph is symmetric: vertex u is adjacent to vertex v if and only if v is adjacent to u.
Or.inl- Given a proof of A, constructs a proof of the disjunction A ∨ B.
Or.inr- Given a proof of B, constructs a proof of the disjunction A ∨ B.
- In informal proofs, one typically invokes symmetry between the endpoints of an edge to consider a single case; the formal proof explicitly checks all four endpoint pairings across both intersections (edges pq with ab, and pq with uv).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- If a simple graph with at least one edge is triangle-free and every two edges intersect, then all edges share a common vertex. -/theorem triangle_free_edges_share_endpoint {V : Type*} (H : SimpleGraph V) (he : ∃ a b : V, H.Adj a b) (htri : H.CliqueFree 3) (hpair : ∀ u v x y : V, H.Adj u v → H.Adj x y → u = x ∨ u = y ∨ v = x ∨ v = y) : ∃ c : V, ∀ u v : V, H.Adj u v → u = c ∨ v = c := by classical have tri_contra : ∀ {x y z : V}, H.Adj x y → H.Adj y z → H.Adj x z → x ≠ y → x ≠ z → y ≠ z → False := by intro x y z hxy hyz hxz hne1 hne2 hne3 apply htri ({x, y, z} : Finset V) rw [SimpleGraph.isNClique_iff] constructor · rw [SimpleGraph.isClique_iff] simp [Set.Pairwise, hxy, hyz, hxz, H.adj_comm] · simp [hne1, hne2, hne3] obtain ⟨a, b, hab⟩ := he by_cases halla : ∀ u v : V, H.Adj u v → u = a ∨ v = a · exact ⟨a, halla⟩ · push Not at halla obtain ⟨p, q, hpq, hpa, hqa⟩ := halla have hpbq : p = b ∨ q = b := by rcases hpair p q a b hpq hab with h | h | h | h · exact absurd h hpa · exact Or.inl h · exact absurd h hqa · exact Or.inr h refine ⟨b, ?_⟩ intro u v huv by_contra hcon push Not at hcon obtain ⟨hub, hvb⟩ := hcon have hua_or_hva : u = a ∨ v = a := by rcases hpair u v a b huv hab with h | h | h | h · exact Or.inl h · exact absurd h hub · exact Or.inr h · exact absurd h hvb rcases hpbq with hpb | hqb · rcases hua_or_hva with hua | hva · have hqv : q = v := by rcases hpair p q u v hpq huv with h | h | h | h · exact absurd (by rw [← hua, ← h, hpb] : a = b) hab.ne · exact absurd (by rw [← h, hpb] : v = b) hvb · exact absurd (by rw [h, hua] : q = a) hqa · exact h rw [hpb] at hpq rw [hua, hqv.symm] at huv exact tri_contra hab hpq huv hab.ne hqa.symm hpq.ne · have hqu : q = u := by rcases hpair p q u v hpq huv with h | h | h | h · exact absurd (by rw [← h, hpb] : u = b) hub · exact absurd (by rw [← hva, ← h, hpb] : a = b) hab.ne · exact h · exact absurd (by rw [h, hva] : q = a) hqa rw [hpb] at hpq rw [hva, hqu.symm] at huv exact tri_contra hab hpq huv.symm hab.ne hqa.symm hpq.ne · rcases hua_or_hva with hua | hva · have hpv : p = v := by rcases hpair p q u v hpq huv with h | h | h | h · exact absurd (by rw [h, hua] : p = a) hpa · exact h · exact absurd (by rw [← hua, ← h, hqb] : a = b) hab.ne · exact absurd (by rw [← h, hqb] : v = b) hvb rw [hqb] at hpq rw [hua, hpv.symm] at huv exact tri_contra hab hpq.symm huv hab.ne hpa.symm hpq.ne.symm · have hpu : p = u := by rcases hpair p q u v hpq huv with h | h | h | h · exact h · exact absurd (by rw [← hva, h] : p = a) hpa · exact absurd (by rw [← h, hqb] : u = b) hub · exact absurd (by rw [← hva, ← h, hqb] : a = b) hab.ne rw [hqb] at hpq rw [hva, hpu.symm] at huv exact tri_contra hab hpq.symm huv.symm hab.ne hpa.symm hpq.ne.symm