subdivided_k33_line_graph_isk4_diamond_free_four_chromatic
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
- h_subdivided_k33The 7-vertex graph obtained by subdividing one edge of the complete bipartite graph K_{3,3} exactly once.
- has_induced_k4_subdivisionA graph G contains an induced subdivision of K4: there are four distinct branch vertices and one simple path for each of their six…
- is_diamond_freeA simple graph G is diamond-free if it does not contain the diamond graph as an induced subgraph.
- k4_claw_diamond_free_has_no_induced_k4_subdivisionEvery simple graph containing neither an induced K4, an induced claw, nor an induced diamond contains no induced subdivision of K4.
- subdivided_k33_line_graph_no_k4_claw_diamondThe line graph of the once-subdivided K3,3 has no induced K4, claw, or diamond.
- subdivided_k33_line_graph_chromatic_number_eq_fourThe line graph of the graph obtained by subdividing one edge of K3,3 once has chromatic number exactly four.
- IsClawFreeA simple graph G is claw-free if it does not contain the complete bipartite graph K_{1,3} as an induced subgraph.
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.
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).
uses
subdivided_k33_line_graph_no_k4_claw_diamondrcases subdivided_k33_line_graph_no_k4_claw_diamond with ⟨hK, hc, hd⟩
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`.
uses
k4_claw_diamond_free_has_no_induced_k4_subdivision,subdivided_k33_line_graph_chromatic_number_eq_fourexact ⟨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
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.
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⟩