<p>There is no such function - here is an example where $h(G)$ is arbitrarily large while $h(G/M) \leq 4$. Make $G$ by taking two copies of an $n \times n$ grid and making every vertex of one grid adjacent to the corresponding vertex of the other grid.</p>

<p>$G$ contains a clique of size $n$ as a minor (i.e $h(G) \geq n$). In particular the $i$'th vertex of the clique is obtained by contracting the $i$'th row of the first grid and the $i$'th column of the second grid and then contracting these two vertices together.</p>

<p>Let $M$ be the matching that connects each vertex of the first grid with its copy in the second grid. $G/M$ is an $n \times n$ grid, so $G/M$ is planar and hence $h(G/M) \leq 4$.</p>

CC BY-SA 3.0
2017-05-18T20:08:01.400Z
2017-05-18T20:08:01.400Z
daniello
<p>Given a graph $G$ with Hadwiger number $h(G)$ and a matching $M$ of $G$. Let $G/M$ be the simple graph obtained by contracting $M$. I am looking for a lower bound on the Hadwiger number of $G/M$ as a function of $h(G)$, say: $$h(G/M) \geq \Omega(\log h(G))$$ (or something like that), or a counter example to show that there is no such bound. Does anybody have any pointer on this?</p>

<p>I think the right bound is: $$h(G/M) = \Omega(h(G))$$
but I am unable to prove (or disprove) it. This is based on two observations: contracting a matching of $K_h$ resulting in $K_{h/2}$ and the similar situation holds for treewidth parameter: contracting a matching of a treewidth $k$ graph resulting in a graph of treewidth at least $k/2$ (though treewidth is loosely connected to Hadwiger number). </p>

<p>From Wikipedia: Hadwiger number $h(G)$ is the largest number $k$ for which the complete graph $K_k$ is a minor of $G$.</p>

<graph-theory><graph-minor>
Hadwiger number under matching contraction
Hung Le
# Hadwiger number under matching contraction

(Asked by: username_0 on 2017-05-18)

Given a graph $G$ with Hadwiger number $h(G)$ and a matching $M$ of $G$. Let $G/M$ be the simple graph obtained by contracting $M$. I am looking for a lower bound on the Hadwiger number of $G/M$ as a function of $h(G)$, say: $$h(G/M) \geq \Omega(\log h(G))$$ (or something like that), or a counter example to show that there is no such bound. Does anybody have any pointer on this?

I think the right bound is: $$h(G/M) = \Omega(h(G))$$
but I am unable to prove (or disprove) it. This is based on two observations: contracting a matching of $K\_h$ resulting in $K\_{h/2}$ and the similar situation holds for treewidth parameter: contracting a matching of a treewidth $k$ graph resulting in a graph of treewidth at least $k/2$ (though treewidth is loosely connected to Hadwiger number).

From Wikipedia: Hadwiger number $h(G)$ is the largest number $k$ for which the complete graph $K\_k$ is a minor of $G$.

**Tags:** graph-theory, graph-minor


---

## 1 answers

### Answer by username_1 on 2017-05-18. Score: 8 | Accepted answer

There is no such function - here is an example where $h(G)$ is arbitrarily large while $h(G/M) \leq 4$. Make $G$ by taking two copies of an $n \times n$ grid and making every vertex of one grid adjacent to the corresponding vertex of the other grid.

$G$ contains a clique of size $n$ as a minor (i.e $h(G) \geq n$). In particular the $i$'th vertex of the clique is obtained by contracting the $i$'th row of the first grid and the $i$'th column of the second grid and then contracting these two vertices together.

Let $M$ be the matching that connects each vertex of the first grid with its copy in the second grid. $G/M$ is an $n \times n$ grid, so $G/M$ is planar and hence $h(G/M) \leq 4$.


---

