Home ยป What is the smallest number of disjoint spanning trees made a graph Hamiltonian

Is this statement correct?

On September 10th, 2007 mdevos says:

Unless I am mistaken, it appears that there does not exist any $ k $ for which any of the above problems has a positive solution. For instance, let $ G $ be the complete graph with vertex set $ V = \{1,\ldots,6k\} $, and define $ C $ to be the edge-cut of $ G $ consisting of all edges between $ \{1,2,\ldots,2k\} $ and $ \{2k+1,2k+2,\ldots,6k\} $. Now define a weighting of $ G $ by assigning each edge in $ C $ weight 1 and every other edge weight 2. So, the subgraph $ (V,C) $ (consisting of all edges of weight 1) is isomorphic to $ K_{2k,4k} $ - and since $ K_{2k,4k} $ has $ k $ edge-disjoint spanning trees (by the Nash-Williams theorem, say), our procedure may well choose trees $ T_1,T_2,\ldots,T_k $ so that all of the edges in all of these graphs are in $ C $. But then $ T^k $ will not have a Hamiltonian path since it is a subgraph of $ (V,C) \cong K_{2k,4k} $.

Of course, we may modify the edge weights here so that the procedure is forced to choose $ T_1,\ldots,T_k $ so that all of these trees have their edges in $ C $.

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options