AFTD Auto-Formalizing Theoretical Domains

subdivided_k33_line_graph_isk4_diamond_free_four_chromatic

theoremverifiedformalization

Let H be the graph obtained from K3,3 by subdividing one edge exactly once, and let G be its line graph. Then G has no induced subdivision of K4, has no induced diamond, and has chromatic number exactly four.

Statement

theorem subdivided_k33_line_graph_isk4_diamond_free_four_chromatic :
    (¬ has_induced_k4_subdivision h_subdivided_k33.lineGraph) ∧
    is_diamond_free h_subdivided_k33.lineGraph ∧
    h_subdivided_k33.lineGraph.chromaticNumber = 4
Formalizes
arXiv:2610.32404 Proposition 11.2, with H as constructed in Section 11.
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7

Read back from the Lean

The theorem asserts that the line graph of h_subdivided_k33 satisfies three properties: 1. It does not contain an induced subdivision of $K_4$ (¬ has_induced_k4_subdivision). 2. It is diamond-free (is_diamond_free), meaning it contains no induced subgraph isomorphic to the diamond graph $K_4 \setminus \{e\}$. 3. Its chromatic number is equal to 4 (chromaticNumber = 4).

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 combines the forbidden induced subgraphs of the line graph of the singly subdivided K3,3 with a general characterization theorem. Specifically, the line graph is known to be K4-free, claw-free, and diamond-free. A general theorem guarantees that any graph satisfying these three forbidden-subgraph conditions contains no induced subdivision of K4. Together with diamond-freeness and the previously established chromatic number of 4, the conjunction follows directly.

  1. The line graph of the singly subdivided K3,3 contains no induced K4, is claw-free, and is diamond-free.

    We unpack the established structural properties of the line graph given by `subdivided_k33_line_graph_no_k4_claw_diamond`, obtaining hypotheses that the graph contains no induced K4 (hK), is claw-free (hc), and is diamond-free (hd).

    line 5

    uses subdivided_k33_line_graph_no_k4_claw_diamond

      rcases subdivided_k33_line_graph_no_k4_claw_diamond with ⟨hK, hc, hd⟩
  2. The line graph has no induced K4 subdivision, is diamond-free, and has chromatic number 4.

    We establish the three parts of the conjunction directly: applying `k4_claw_diamond_free_has_no_induced_k4_subdivision` to the hypotheses (hK, hc, hd) proves that the line graph has no induced K4 subdivision; diamond-freeness is given by hd; and the chromatic number is 4 by `subdivided_k33_line_graph_chromatic_number_eq_four`.

    line 6

    uses k4_claw_diamond_free_has_no_induced_k4_subdivision, subdivided_k33_line_graph_chromatic_number_eq_four

      exact ⟨k4_claw_diamond_free_has_no_induced_k4_subdivision _ hK hc hd, hd, subdivided_k33_line_graph_chromatic_number_eq_four⟩
subdivided_k33_line_graph_no_k4_claw_diamond
The line graph of the singly subdivided K3,3 contains no induced K4, is claw-free, and is diamond-free.
k4_claw_diamond_free_has_no_induced_k4_subdivision
If a graph contains no induced K4, is claw-free, and is diamond-free, then it contains no induced subdivision of K4.
subdivided_k33_line_graph_chromatic_number_eq_four
The chromatic number of the line graph of the singly subdivided K3,3 is 4.

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 subdivided_k33_line_graph_isk4_diamond_free_four_chromatic :    (¬ has_induced_k4_subdivision h_subdivided_k33.lineGraph) ∧    is_diamond_free h_subdivided_k33.lineGraph ∧    h_subdivided_k33.lineGraph.chromaticNumber = 4 := by  rcases subdivided_k33_line_graph_no_k4_claw_diamond with ⟨hK, hc, hd⟩  exact ⟨k4_claw_diamond_free_has_no_induced_k4_subdivision _ hK hc hd, hd, subdivided_k33_line_graph_chromatic_number_eq_four⟩
See it in the graphDiscuss this resultChallenge it