# Increasing Hadwiger number by collapsing vertices of distance $2$

If $$G=(V,E)$$ is a finite, simple, undirected graph, the Hadwiger number $$\eta(G)$$ is defined to be the size of the largest complete minor of $$G$$.

Is there a finite graph $$G=(V,E)$$ with the following property?

Whenever $$v,w\in V$$ have distance $$2$$, the Hadwiger number of the graph obtained by collapsing $$v,w$$ is strictly larger than $$\eta(G)$$.

## 1 Answer

Well, if you collapse all vertices of distance 2 in a connected graph, then the resulting graph will either be a single vertex (if the graph is not bipartite) or an edge.

But there are graphs where you can identify some of the vertices of distance 2 from each other to increase $$\eta(G)$$.

Indeed,

1. First let $$G$$ be a $$K+1$$-clique where $$K$$ is of the form e.g. $$K=d(d-1)$$ for some integer $$d \geq 3$$.

2. Now subdivide each edge in $$G$$ to a path with say 5 vertices and call the resulting graph $$G'$$. Then every vertex of degree greater than 2 in $$G'$$ has degree $$K$$, and $$\eta(G)$$ is still $$K+1$$.

3. Now replace every vertex $$v$$ in $$G'$$ of degree $$K$$ with a complete $$d$$-ary tree $$T_v$$ with $$K=d(d-1)$$ leaves and write the set of $$K$$ leafs in $$T_v$$ as $$\{u_{vv'}; v'$$ another vertex in $$G'$$ of degree $$K\}$$--for every two vertices $$v,v'$$ of degree $$K$$ in $$G'$$, there is now a path from $$u_{vv'}$$ of $$T_v$$ to $$u_{v'v}$$ of $$T_{v'}$$ (every vertex and edge in the interior of this past is the same in $$H$$ as it was in $$G'$$). Call the resulting graph $$H$$.

4. Then $$\eta(H) \le d < K < \eta(G)$$. However, identifying in $$H$$ all vertices of distance 2 in each of the $$T_v$$s results in a graph that is close enough to $$G'$$ and as rthe same Hadwiger number as $$G'$$. Indeed this collapses each $$T_v$$ to an edge where one endpoint has degree $$K$$ (and the other endpoint is incident to no more edges). In fact this resulting graph has $$G'$$ as a subgraph--indeed every vertex of degree $$K$$ in $$G'$$ is incident to another edge where the endpoint is an isolated vertex.

• Thanks for your answer! My question was not, what happens if I identify all vertices that have distance $2$, but my question was: what is an example of a graph $G=(V,E)$ such that *whenever* I pick $v,w\in V$ such that $v,w$ have distance $2$, then the Hadwiger number is increased. Should I reformulate the question? – Dominic van der Zypen Feb 4 '19 at 7:42
• Just edited the question to (hopefully) make it clearer – Dominic van der Zypen Feb 4 '19 at 7:45