AFTD Auto-Formalizing Theoretical Domains

op_1058_of_diam_le_two

theoremverifiedoriginal

For any finite connected simple graphs G and H of diameter at most 2, if at least one of G and H is well-covered, then at least one of G and H has the well-covered powers property.

Statement

theorem op_1058_of_diam_le_two {V W : Type*} [Fintype V] [Fintype W]
    (G : SimpleGraph V) (H : SimpleGraph W)
    (hG : G.Connected) (hH : H.Connected)
    (hdG : G.diam ≤ 2) (hdH : H.diam ≤ 2)
    (hwc : simple_graph_is_well_covered G ∨ simple_graph_is_well_covered H) :
    simple_graph_has_well_covered_powers G ∨ simple_graph_has_well_covered_powers H
Related work
arXiv:2611.03956 Question 1.1
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

Read back from the Lean

Let V and W be finite types. Let G be a simple graph on V and H be a simple graph on W. Assume that: 1. G is connected (G.Connected), 2. H is connected (H.Connected), 3. the diameter of G is at most 2 (G.diam ≤ 2), 4. the diameter of H is at most 2 (H.diam ≤ 2), and 5. G is well-covered or H is well-covered (simple_graph_is_well_covered G ∨ simple_graph_is_well_covered H). Then G has well-covered powers or H has well-covered powers (simple_graph_has_well_covered_powers G ∨ simple_graph_has_well_covered_powers H).

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

The proof splits into cases on the assumption that at least one of G or H is well-covered. In each branch, the well-covered factor is finite, connected, and has diameter at most 2, so an established lemma immediately yields that all of its graph powers are well-covered. Thus, at least one of the two graphs has well-covered powers.

  1. If G is well-covered, then G has well-covered powers, satisfying the disjunction.

    We perform case analysis on the hypothesis hwc, which asserts that at least one of G or H is well-covered. In the first case, G is well-covered (hG_wc). To prove the disjunction, it suffices to prove the left alternative, namely that G has well-covered powers. Since G is finite, connected (hG), has diameter at most 2 (hdG), and is well-covered (hG_wc), the lemma forall_power_well_covered_of_well_covered_diam_le_two applies directly to establish that G has well-covered powers.

    lines 8–11

    uses forall_power_well_covered_of_well_covered_diam_le_two

      cases hwc with
      | inl hG_wc =>
        left
        exact forall_power_well_covered_of_well_covered_diam_le_two G hG hdG hG_wc
  2. If H is well-covered, then H has well-covered powers, satisfying the disjunction.

    In the second case, H is well-covered (hH_wc). It suffices to prove the right alternative, namely that H has well-covered powers. Applying forall_power_well_covered_of_well_covered_diam_le_two to H, using its connectedness (hH), diameter bound (hdH), and well-coveredness (hH_wc), establishes that H has well-covered powers.

    lines 12–14

    uses forall_power_well_covered_of_well_covered_diam_le_two

      | inr hH_wc =>
        right
        exact forall_power_well_covered_of_well_covered_diam_le_two H hH hdH hH_wc
forall_power_well_covered_of_well_covered_diam_le_two
If a finite simple graph is connected, has diameter at most 2, and is well-covered, then each of its powers Gᵈ (for d ≥ 1) is also well-covered.

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

/-- For graphs of diameter at most 2, if at least one factor is well-covered, then at least one factor has well-covered powers. -/theorem op_1058_of_diam_le_two {V W : Type*} [Fintype V] [Fintype W]    (G : SimpleGraph V) (H : SimpleGraph W)    (hG : G.Connected) (hH : H.Connected)    (hdG : G.diam ≤ 2) (hdH : H.diam ≤ 2)    (hwc : simple_graph_is_well_covered G ∨ simple_graph_is_well_covered H) :    simple_graph_has_well_covered_powers G ∨ simple_graph_has_well_covered_powers H := by  cases hwc with  | inl hG_wc =>    left    exact forall_power_well_covered_of_well_covered_diam_le_two G hG hdG hG_wc  | inr hH_wc =>    right    exact forall_power_well_covered_of_well_covered_diam_le_two H hH hdH hH_wc
See it in the graphDiscuss this resultChallenge it