The star chromatic index of is six
ProvedOPG37271.k33_exact_sixFor 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,
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.
import Definitions.Def_opg37271_star_edge_coloring
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 OPG37271Read-back
What the Lean code literally says, in plain math · gpt-5.6-luna
The theorem asserts that for the complete bipartite graph , 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 using the six colors such that: for every vertex and distinct neighbors of , the colors assigned to and are different; there do not exist five pairwise distinct vertices with all four consecutive edges present and with the color of equal to that of and the color of equal to that of ; and there do not exist four pairwise distinct vertices with all four cycle edges present and with the colors of opposite edges equal and the colors of equal. In addition, there does not exist any edge-coloring of the same graph using the five colors that satisfies all three of these conditions. Here an edge-coloring assigns a color to every edge of .
Confirmed by the mission captain (proposal self-audit).