-2
$\begingroup$

Let $G=(V,E)$ be a simple, undirected graph.

We call a partition ${\cal P}$ of a non-empty subset of $V$ a Hadwiger partition if

  1. every block (member of ${\cal P}$) is non-empty and connected, and
  2. if $x, y \in {\cal P}$ are distinct blocks then there are $v\in x$ and $w \in y$ such that $\{v,w\} \in E$.

The Hadwiger number $\eta(G)$ is the maximum number of blocks a Hadwiger partition can have.

Let $n=\eta(G)$ and suppose that every Hadwiger partition of $G$ into $n$ blocks contains at least one block consisting of 1 vertex only ("singleton block"). Does this imply that there is $v\in V$ such that $\eta(G\setminus\{v\}) = n-1$?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

The graph $G=2K_n$ is a counterexample. Or, if $G$ is supposed to be connected, then $G=2K_n+e\ $ (that's $2K_n$ with an additional edge) is a counterexample for $n\ge3.$

$\endgroup$

You must log in to answer this question.

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