Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

The star chromatic index of K3,3K_{3,3}K3,3​ is six

Proved
OPG37271.k33_exact_six

by hao jia · Sep 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsedge-coloringgraph-theoryopen-problem

For the complete bipartite graph with two parts of three vertices, there exists a star edge coloring using six colors, and no star edge coloring using five colors exists. Equivalently,

χs′(K3,3)=6.\chi'_s(K_{3,3})=6.χs′​(K3,3​)=6.

Both assertions use proper edge colorings and prohibit bichromatic simple paths and cycles of four edges. This exact value shows that a universal six-color theorem for subcubic graphs would be sharp.

Preamble
import Definitions.Def_opg37271_star_edge_coloring
Formal statement
namespace OPG37271

/-- The complete bipartite graph K₃,₃ is star edge colorable with six colors
but not with five, showing that the conjectured six-color bound is sharp. -/
theorem k33_exact_six :
    HasStarEdgeColoring (completeBipartiteGraph (Fin 3) (Fin 3)) 6 ∧
    ¬ HasStarEdgeColoring (completeBipartiteGraph (Fin 3) (Fin 3)) 5 := by sorry

end OPG37271
Source
Lei--Shi--Song, Star chromatic index of subcubic multigraphs, J. Graph Theory 88 (2018), 566--576, https://arxiv.org/abs/1701.04105v3, Section 1, paragraph following Theorem 1.3
Read-back

What the Lean code literally says, in plain math · gpt-5.6-luna

The theorem asserts that for the complete bipartite graph G=K3,3G=K_{3,3}G=K3,3​, whose vertices are the disjoint union of two parts each containing three elements and whose edges are exactly all pairs joining different parts, there exists an edge-coloring ccc using the six colors Fin 6\mathrm{Fin}\,6Fin6 such that: for every vertex vvv and distinct neighbors u,wu,wu,w of vvv, the colors assigned to vuvuvu and vwvwvw are different; there do not exist five pairwise distinct vertices v0,v1,v2,v3,v4v_0,v_1,v_2,v_3,v_4v0​,v1​,v2​,v3​,v4​ with all four consecutive edges present and with the color of v0v1v_0v_1v0​v1​ equal to that of v2v3v_2v_3v2​v3​ and the color of v1v2v_1v_2v1​v2​ equal to that of v3v4v_3v_4v3​v4​; and there do not exist four pairwise distinct vertices v0,v1,v2,v3v_0,v_1,v_2,v_3v0​,v1​,v2​,v3​ with all four cycle edges v0v1,v1v2,v2v3,v3v0v_0v_1,v_1v_2,v_2v_3,v_3v_0v0​v1​,v1​v2​,v2​v3​,v3​v0​ present and with the colors of opposite edges v0v1,v2v3v_0v_1,v_2v_3v0​v1​,v2​v3​ equal and the colors of v1v2,v3v0v_1v_2,v_3v_0v1​v2​,v3​v0​ equal. In addition, there does not exist any edge-coloring of the same graph using the five colors Fin 5\mathrm{Fin}\,5Fin5 that satisfies all three of these conditions. Here an edge-coloring assigns a color to every edge of GGG.

Human review
  • Endorsed by Shuze Chen · Sep 7, 2026

  • Endorsed by hao jia · Sep 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactJoin Slack© 2026 Prove2Me