AFTD Auto-Formalizing Theoretical Domains

simple_graph_no_leaf_of_power_well_covered

theoremverifiedformalization

Let G be a finite connected graph of diameter D ≥ 2 such that G^{D−1} is well-covered. Then G has no leaves (no vertex of degree 1).

Statement

theorem simple_graph_no_leaf_of_power_well_covered {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) (hD : 2 ≤ G.diam)
    (hwc : simple_graph_is_well_covered (simple_graph_power G (G.diam - 1))) (v : V) :
    G.degree v ≠ 1
Formalizes
arXiv:2610.09300 (On graphs whose powers are well-covered), Corollary 2.6.
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • simple_graph_eccent_eq_diam_of_power_well_coveredLet G be a finite connected graph of diameter D ≥ 2 such that G^{D−1} is well-covered. Then every vertex of G has eccentricity D (G is…
  • simple_graph_is_well_coveredA finite graph is well-covered if all its maximal independent sets have the same cardinality (equivalently, all its minimal vertex covers…
  • simple_graph_powerThe d-th power G^d of a graph G: same vertices, two distinct vertices adjacent iff they are joined by a path (equivalently a walk) of…
Used by 1

The proof, explained

We argue by contradiction: suppose G has a leaf v, and let u be its unique neighbor. Because the power graph G^{D-1} is well-covered and D = diam(G) ≥ 2, every vertex has eccentricity D, so eccent(u) = D. On the other hand, eccent(u) ≤ D - 1: the distance from u to v is 1 ≤ D - 1, and for any w ≠ v, any shortest walk from v to w must start by stepping to u, so edist(u, w) ≤ edist(v, w) - 1 ≤ D - 1. The two bounds give D ≤ D - 1, an impossibility.

  1. Assume for contradiction that v has degree 1, and obtain its unique neighbor u.

    Suppose for contradiction that G has a leaf v, meaning deg(v) = 1 (hdeg). By SimpleGraph.degree_eq_one_iff_existsUnique_adj, a vertex has degree 1 if and only if it has a unique neighbor. Let u be this unique neighbor, so v is adjacent to u and any neighbor of v must equal u.

    lines 5–6

    uses SimpleGraph.degree_eq_one_iff_existsUnique_adj

      intro hdeg
      obtain ⟨u, hvu, huniq⟩ := (SimpleGraph.degree_eq_one_iff_existsUnique_adj).1 hdeg
  2. The diameter of G is finite and the eccentricity of u equals the diameter of G.

    Since G is connected and finite, the vertex set is nonempty and the extended diameter ediam(G) is finite by SimpleGraph.connected_iff_ediam_ne_top. Hence the integer diameter diam(G) coerced to ℕ∞ equals ediam(G) (using SimpleGraph.diam and ENat.natCast_toNat). Because G^{diam(G)-1} is well-covered and diam(G) ≥ 2, the prior lemma simple_graph_eccent_eq_diam_of_power_well_covered implies that every vertex has eccentricity equal to diam(G), so eccent(u) = diam(G).

    lines 7–11

    uses SimpleGraph.connected_iff_ediam_ne_top, SimpleGraph.diam, ENat.natCast_toNat, simple_graph_eccent_eq_diam_of_power_well_covered

      have : Nonempty V := hconn.nonempty
      have htop : G.ediam ≠ ⊤ := (SimpleGraph.connected_iff_ediam_ne_top).1 hconn
      have hdiam : (G.diam : ℕ∞) = G.ediam := by
        rw [SimpleGraph.diam]; exact ENat.natCast_toNat htop
      have hecc := simple_graph_eccent_eq_diam_of_power_well_covered G hconn hD hwc u
  3. To bound the eccentricity of u by diam(G) - 1, it suffices to bound the distance from u to any vertex w by diam(G) - 1.

    By SimpleGraph.eccent_le_iff, the eccentricity of u is at most a bound k if and only if the distance from u to every vertex is at most k. Setting k = diam(G) - 1, we introduce an arbitrary vertex w and aim to show edist(u, w) ≤ diam(G) - 1.

    lines 12–14

    uses SimpleGraph.eccent_le_iff

      have hle : G.eccent u ≤ ((G.diam - 1 : ℕ) : ℕ∞) := by
        rw [SimpleGraph.eccent_le_iff]
        intro w
  4. In the case w = v, the distance between u and w is 1, which is at most diam(G) - 1.

    We perform a case split on whether w = v. If w = v, the distance edist(u, v) equals edist(v, u) = 1 because u and v are adjacent (SimpleGraph.edist_comm, SimpleGraph.edist_eq_one_iff_adj). Since diam(G) ≥ 2, linear arithmetic (omega) closes the inequality 1 ≤ diam(G) - 1.

    lines 15–18

    uses SimpleGraph.edist_comm, SimpleGraph.edist_eq_one_iff_adj

        by_cases hwv : w = v
        · subst hwv
          rw [SimpleGraph.edist_comm, SimpleGraph.edist_eq_one_iff_adj.2 hvu]
          norm_cast; omega
  5. In the case w ≠ v, any shortest walk from v to w must pass through u, establishing edist(u, w) ≤ diam(G) - 1 and thus eccent(u) ≤ diam(G) - 1.

    When w ≠ v, connectivity guarantees a walk p from v to w whose length equals edist(v, w) (exists_walk_length_eq_edist). The walk p cannot be the empty walk nil because w ≠ v. Thus p starts with an edge from v to some vertex x, followed by a walk p' from x to w. Since x is adjacent to v, uniqueness of v's neighbor forces x = u. The length of p is p'.length + 1 by SimpleGraph.Walk.length_cons. Since edist(v, w) ≤ diam(G) by SimpleGraph.edist_le_ediam, we have p'.length + 1 ≤ diam(G), which gives p'.length ≤ diam(G) - 1. Finally, edist(u, w) ≤ p'.length by SimpleGraph.edist_le, yielding edist(u, w) ≤ diam(G) - 1. This completes the bound eccent(u) ≤ diam(G) - 1 for all w.

    lines 19–31

    uses exists_walk_length_eq_edist, SimpleGraph.edist_le, SimpleGraph.edist_le_ediam, SimpleGraph.Walk.length_cons

        · obtain ⟨p, hp⟩ := (hconn v w).exists_walk_length_eq_edist
          cases p with
          | nil => exact absurd rfl hwv
          | cons h p' =>
            rename_i x
            have hx : x = u := huniq x h
            subst hx
            have h1 : G.edist x w ≤ p'.length := SimpleGraph.edist_le p'
            have h2 : G.edist v w ≤ G.diam := by rw [hdiam]; exact SimpleGraph.edist_le_ediam
            rw [← hp, SimpleGraph.Walk.length_cons] at h2
            have h3 : p'.length + 1 ≤ G.diam := by exact_mod_cast h2
            calc G.edist x w ≤ p'.length := h1
              _ ≤ ((G.diam - 1 : ℕ) : ℕ∞) := by norm_cast; omega
  6. The equality eccent(u) = diam(G) and the inequality eccent(u) ≤ diam(G) - 1 yield a contradiction.

    Substituting eccent(u) = diam(G) into the inequality eccent(u) ≤ diam(G) - 1 gives diam(G) ≤ diam(G) - 1. Linear arithmetic (omega) derives False from diam(G) ≤ diam(G) - 1 and diam(G) ≥ 2, contradicting the existence of the leaf v.

    lines 32–34

      rw [hecc] at hle
      norm_cast at hle
      omega
ENat.natCast_toNat
Casting an extended natural number n to ℕ and back yields n, provided n is finite (n ≠ ⊤).
SimpleGraph.connected_iff_ediam_ne_top
A nonempty finite simple graph is connected if and only if its extended diameter is not ⊤.
SimpleGraph.degree_eq_one_iff_existsUnique_adj
A vertex in a simple graph has degree 1 if and only if there exists a unique vertex adjacent to it.
SimpleGraph.diam
The diameter of a simple graph is defined as the natural number obtained by truncating its extended diameter.
SimpleGraph.eccent_le_iff
The eccentricity of a vertex u is at most k if and only if the extended distance from u to every vertex is at most k.
SimpleGraph.edist_comm
Extended distance in a simple graph is symmetric: edist u v = edist v u.
SimpleGraph.edist_eq_one_iff_adj
In a simple graph, two vertices have extended distance 1 if and only if they are adjacent.
SimpleGraph.edist_le
The extended distance between two vertices is at most the length of any walk connecting them.
SimpleGraph.edist_le_ediam
The extended distance between any two vertices in a graph is at most the graph's extended diameter.
SimpleGraph.Walk.length_cons
Prepending an edge to a walk increases its length by 1.
exists_walk_length_eq_edist
Between any two reachable vertices, there exists a walk whose length equals their extended distance.
simple_graph_eccent_eq_diam_of_power_well_covered
In a finite connected graph of diameter D ≥ 2 whose power G^{D-1} is well-covered, every vertex has eccentricity equal to D.

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

theorem simple_graph_no_leaf_of_power_well_covered {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) (hD : 2 ≤ G.diam)    (hwc : simple_graph_is_well_covered (simple_graph_power G (G.diam - 1))) (v : V) :    G.degree v ≠ 1 := by  intro hdeg  obtain ⟨u, hvu, huniq⟩ := (SimpleGraph.degree_eq_one_iff_existsUnique_adj).1 hdeg  have : Nonempty V := hconn.nonempty  have htop : G.ediam ≠ ⊤ := (SimpleGraph.connected_iff_ediam_ne_top).1 hconn  have hdiam : (G.diam : ℕ∞) = G.ediam := by    rw [SimpleGraph.diam]; exact ENat.natCast_toNat htop  have hecc := simple_graph_eccent_eq_diam_of_power_well_covered G hconn hD hwc u  have hle : G.eccent u ≤ ((G.diam - 1 : ℕ) : ℕ∞) := by    rw [SimpleGraph.eccent_le_iff]    intro w    by_cases hwv : w = v    · subst hwv      rw [SimpleGraph.edist_comm, SimpleGraph.edist_eq_one_iff_adj.2 hvu]      norm_cast; omega    · obtain ⟨p, hp⟩ := (hconn v w).exists_walk_length_eq_edist      cases p with      | nil => exact absurd rfl hwv      | cons h p' =>        rename_i x        have hx : x = u := huniq x h        subst hx        have h1 : G.edist x w ≤ p'.length := SimpleGraph.edist_le p'        have h2 : G.edist v w ≤ G.diam := by rw [hdiam]; exact SimpleGraph.edist_le_ediam        rw [← hp, SimpleGraph.Walk.length_cons] at h2        have h3 : p'.length + 1 ≤ G.diam := by exact_mod_cast h2        calc G.edist x w ≤ p'.length := h1          _ ≤ ((G.diam - 1 : ℕ) : ℕ∞) := by norm_cast; omega  rw [hecc] at hle  norm_cast at hle  omega
See it in the graphDiscuss this resultChallenge it