AFTD Auto-Formalizing Theoretical Domains

triangle_free_edges_share_endpoint

theoremverified

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.

  1. 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.

    lines 8–17

    uses SimpleGraph.isNClique_iff, SimpleGraph.isClique_iff, Set.Pairwise, H.adj_comm

      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]
  2. 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.

    lines 18–20

      obtain ⟨a, b, hab⟩ := he
      by_cases halla : ∀ u v : V, H.Adj u v → u = a ∨ v = a
      · exact ⟨a, halla⟩
  3. 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).

    lines 21–28

    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
  4. 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).

    lines 29–39

    uses Or.inl, Or.inr

        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
  5. 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.

    lines 40–59

        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
  6. 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.

    lines 60–78

        · 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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it