Are there $2$ non-adjacent points in the icosahedron graph $G$ such that contracting them leaves the Hadwiger number unchanged?
$\begingroup$
$\endgroup$
1
asked Mar 18, 2019 at 4:46
-
3$\begingroup$ Up to symmetry, there's clearly only two graphs obtained by contracting. Why not simply do it? $\endgroup$– verretMar 28, 2019 at 6:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
No.
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.
