Dirac Graphs Without a Spanning Near-Square of an Odd Cycle: A Negative Answer to a Question of Heinig

At the 2014 Oberwolfach workshop on combinatorics, P. Heinig asked whether, for every odd \(n\ge 7\), every \(n\)-vertex graph with minimum degree at least \(\lceil n/2\rceil\) contains a spanning copy of the graph obtained from the square of an \(n\)-cycle by deleting every other edge on the periphery until exactly three consecutive vertices of degree \(4\) remain. A positive answer would have given a structural reason why the Hamilton cycles of such graphs generate their cycle space. We show that the answer is negative for every odd \(n\ge 7\), under both natural readings of “periphery”, and for \(n=9\) under every reading. The counterexample is the complete bipartite graph \(K_{(n+1)/2,(n-1)/2}\) with a perfect matching, or a matching and one path with two edges, added inside the larger side; for \(n=7\) it is the graph that Heinig himself used as a positive example for the cycle-space question. The proof classifies the independent sets of size \((n-1)/2\) in Heinig’s graph. The cycle-space question itself has since been settled for all large odd \(n\) by Hou and Yin, and it is not affected. This is an unrefereed note.