{"id":"arxiv/2606.18462","url":"https://arxiv.org/abs/2606.18462","tags":["math.CO"],"score":0,"title":"Exact 6-cut rigidity and small-order superconnectivity for the 6-regular case of Dirac's k=4 problem","domain":"math.CO","source":"arxiv","authors":["Alper Ferudun"],"reviews":0,"subject":"math.CO","summary":"Dirac asked in 1970 whether for every k >= 4 there is a k-vertex-critical graph without critical edges; Jensen settled all k >= 5, and only k=4 remains open. Following Skottova and Steiner, call a graph G a (4,1)-graph if chi(G)=4, chi(G-v)=3 for every vertex v, and chi(G-e)=4 for every edge e; they proved delta(G) >= 6 and lambda(G) >= 6 for every (4,1)-graph and asked whether a 6-regular (4,1)-graph exists. We prove three results about this 6-regular case. Theorem A (computational): there is no 6-regular 4-vertex-critical graph on n <= 15 vertices, except for a unique graph (up to…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-16","reactions":{}}