3
$\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

  1. every Hadwiger partition of $G$ into $n$ blocks contains at least one block consisting of 1 vertex only ("singleton block"), and
  2. for all $v\in V$ we have $\eta(G\setminus\{v\}) = n$.

Does this imply that $|V|\geq 2n$?

MOTIVATION: In the answer to this question, @bof gave excellent and short examples for graphs fulfilling conditions 1 and 2 above, each having exactly $2n$ vertices. It's not hard to find other examples with at least this number of vertices. So now, it's open season for smaller examples -- if they exist!

$\endgroup$
3
  • $\begingroup$ can you give an example of such a graph with $|V|\ge 2n$? $\endgroup$ Commented Jan 4, 2016 at 13:58
  • $\begingroup$ Yes, 2 copies of $K_n$, see mathoverflow.net/a/227483/8628 $\endgroup$ Commented Jan 4, 2016 at 19:55
  • 1
    $\begingroup$ The singleton block condition seems redundant as for at most 2n-1 vertices you can just apply the pigeonhole principle. $\endgroup$
    – domotorp
    Commented Jan 5, 2016 at 22:57

1 Answer 1

2
+50
$\begingroup$

Octahedron$ .$

$\endgroup$
4
  • $\begingroup$ Can you elaborate? I suppose you found a counterexample.. $\endgroup$ Commented Jan 6, 2016 at 8:20
  • $\begingroup$ Yes, an octahedron seems to serve as a counterexample. $\endgroup$ Commented Jan 7, 2016 at 16:07
  • $\begingroup$ Please explain what an octahedron is and why it is a counterexample, Ilya or domotorp, so I can accept the answer and award the bounty. $\endgroup$ Commented Jan 9, 2016 at 12:17
  • $\begingroup$ mathworld.wolfram.com/OctahedralGraph.html $\endgroup$
    – domotorp
    Commented Jan 9, 2016 at 21:18

You must log in to answer this question.

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