-2
$\begingroup$

Suppose $G$ is a finite simple graph. Let $h(G)$ denote the Hadwiger number of $G$; that is, the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$.

What is an example of a graph $G_0=(V_0, E_0)$ containing two non-adjacent vertices $v, w\in V_0$ such that when $v$ and $w$ are identified, the Hadwiger number of the resulting graph is smaller than $h(G_0)$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Identify two opposite vertices of the cycle graph $C_4$. This reduces the Hadwiger number from 3 to 2.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .