Are there $2$ non-adjacent points in the icosahedron graph $G$ such that contracting them leaves the Hadwiger number unchanged?


closed as off-topic by Jan-Christoph Schlage-Puchta, Alexey Ustinov, YCor, Pace Nielsen, Ivan Izmestiev Apr 2 at 10:25

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Jan-Christoph Schlage-Puchta, Alexey Ustinov, Pace Nielsen, Ivan Izmestiev
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ Up to symmetry, there's clearly only two graphs obtained by contracting. Why not simply do it? $\endgroup$ – verret Mar 28 at 6:00


The icosahedron graph is distance transitive, meaning that for any two pairs $(a,b)$ and $(c,d)$ of vertices of the icosahedral graph such that $\text{dist}(a,b) = \text{dist}(c,d)$, there is an automorphism $\sigma$ such that $\sigma(a) = c$ and $\sigma(b) = d$. Since the icosahedral graph has diameter 3, there are only two choices of pairs of non-adjacent vertices up to automorphisms: those pairs at distance 2 and those at distance 3. Note that the icosahedral graph is planar, and thus it does not have $K_5$ as a minor. This means that its Hadwiger number is at most 4 (and it is actually equal to this according to Sage). By computation in Sage, you can quickly show that merging two vertices at distance 2 or at distance 3 results in graphs with $K_5$ as a minor, thus the Hadwiger number does increase.


Not the answer you're looking for? Browse other questions tagged or ask your own question.