I have a graph, and I want to get the spanning tree with the fewest spanning tree odd-degree vertices ( counting only edges in the spanning tree ) among all spanning trees in the graph. Of course, an approximate solution is also possible (after all, the time complexity of finding all spanning trees is too high)
I tried to read the paper on finding all spanning trees in a graph, but the time complexity is too high.
As @btilly notes, finding a Hamiltonian path in a cubic graph (an NP-hard problem) is equivalent to finding a spanning tree with only two vertices of odd degree, so this problem is hard in general.
You could try this local search method: starting from an arbitrary initial spanning tree, repeatedly choose a random edge not in the current spanning tree, add it to the tree, examine the resulting fundamental cycle, and delete the edge with the most endpoints of odd degree (leaving another spanning tree).
The graph that you're interested in is the fat-tree graph with k = 20. It's a bipartite graph with k²/4 + k²/2 = 300 nodes on one side (core and edge) and k²/2 = 200 nodes on the other (aggregation). We can show that every spanning tree has at least 102 nodes of odd degree. More generally,
Theorem: for every m ≥ n, for every bipartite graph G with m nodes on the left side and n nodes on the right, every spanning tree T of G has at least 2⌈(m − n + 1)/2⌉ vertices of odd degree (in T).
Proof: The tree T has exactly m + n − 1 edges, each connecting a left node and a right node. Every node in T has degree at least one. Accordingly, letting d be the number of left nodes of odd degree (in T), we derive an inequality
d + 2(m − d) ≤ m + n − 1
since each node of odd degree has at least one incident edge, and each node of even degree has at least two incident edges. Do some algebra:
m − d ≤ n − 1
d ≥ m − n + 1.
We also know by the Handshaking Lemma that the total number of nodes of odd degree is even. Combining these facts yields the conclusion.