Prove that one cannot find a minimum spanning tree in which all vertices have degree less than or equal to 2

Question

Given the following graph, I need to show that it's not possible to find a minimum bounded spanning tree of degree less than or equal to 2, where all edges have weights equal to 1. I haven't been able to come up with an elegant proof for that, only proving the claim rather unrigorously by using a combinatorial argument. Is there an elegant proof for that statement? [1

Answer 1

Observe that the only way that this graph $G$ could have a minimum spanning tree of maximum degree 2 i.e., a Hamiltonian path $P$, is if the Petersen Graph has a Hamiltonian cycle. [Indeed, if $G$ has a Hamiltonian path $P = u_1u_2\ldots u_{12}$ then $P$ must start at the far southeast vertex $u_1$ of $G$ that has degree 1 and end at the far southwest vertex $u_{12}$ of $G$ that has degree 1, with $u_2u_{11}$; $u_2$ the one vertex in $G$ adjacent to $u_1$, and $u_{11}$ the one vertex in $G$ adjacent to $u_{12}$, forming the southern edge of the Petersen graph i.e., the induced subgraph of $G$ on $\{u_2,u_3,\ldots, u_{11}\}$. But then $u_2u_3 \ldots u_{10}u_{11}u_2$ is a Hamiltonian cycle of the Petersen graph.]

However it is well-known that the Petersen graph has no Hamiltonian cycle. See Prove Petersen graph is not Hamiltonian using deduction and no fancy theorems