Let $G$ be a graph, then we define its Hadwiger graph $\textrm{Hadw}(G)$ in the following way:

  • $V(\textrm{Hadw}(G)) = \{S\subseteq (V(G): S\neq \emptyset\textrm{ and } S \textrm{ is connected}\}$;
  • $E(\textrm{Hadw}(G)) = \{\{S,T\}\subseteq V(\textrm{Hadw}(G)): S\cap T = \emptyset \textrm{ and } (\exists s\in S, t\in T): \{s,t\}\in E(G) \}.$

$G$ embeds to $\textrm{Hadw}(G)$ by $v\mapsto \{v\}$, and the Hadwiger conjecture states $\chi(G) \leq \omega(\textrm{Hadw}(G))$.

Question: If $G, H$ are (finite or infinite) graphs, does $\textrm{Hadw}(G) \cong \textrm{Hadw}(H)$ imply $G\cong H$?


$\def\Hadw{\mathop{\rm Hadw}}$This is true for finite graphs, and false for (not necessarily connected) infinite graphs. Right now I do not know what happens for infinite connected graphs.

1. Each component $G_1\subseteq G$ corresponds to an isolated vertex $v_{G_1}$ in $\Hadw(G)$ and a component $\Hadw(G_1)\setminus \{v_{G_1}\}$; this component is empty if $G_1$ consists of an isolated vertex. For finite graphs, this means that we find the number of isolated vertices and the Hadwiger graphs of other components; so the problem reduces to the same problem for finite connected graphs. For infinite graphs, this leads to the counterexample. Let $G$ be a union of a countable number of components none of which is an isolated vertex, and let $H$ be $G$ augmented with an isolated vertex; then $G\not\cong H$ but $\Hadw(G)\cong \Hadw(H)$.

The rest part is devoted to the reconstruction of a connected graph $G$ by its Hadwiger graph.

2. In this case, we will show a bit more, namely:

Knowing $\Hadw(G)$, we can find all the vertices in $\Hadw(G)$ corresponding to the vertices of $G$ (then the induced graph is isomorphic to $G$).

We proceed by the induction on $|V(G)|$. If $|V(G)|=1$ then the statement is obvious.

Any vertex $P\in V(\Hadw(G))$ has degree 1 exactly if $P=V(G)\setminus \{v\}$, where $v\in V(G)$ is not a cut vertex; in this case $\{v\}$ is its only neighbor. Thus we may reconstruct all the vertices of $\Hadw(G)$ which correspond to non-cut vertices of $G$ (notice that there is at least one such vertex!).

Let $T=\{v\}\in V(\Hadw(G))$ be one of such vertices. Denote by $N$ the set of all neighbors of $v$ in $G$; denote $$ L=\{X\in V(\Hadw(G)): (\{v\}\cup N)\subseteq X\}. $$ Notice that $L$ is nonempty.

Consider now the distances $d(S,T)$ from every vertex $S\in V(\Hadw(G))$ (distinct from $T$ and $V(G)$) to $T$.

(i) If $v\notin S$ but $S\cap N\neq\varnothing$ then $d(S,T)=1$.

(ii) If $S\cap(\{v\}\cup N)=\varnothing$ then $d(S,T)=2$ due to a path in $G$ from $v$ to $S$; moreover, in this case $S$ has a neighbor in $L$.

(iii) If $v\in S$ but $N\not\subseteq S$ (that is, $v\in S$ but $S\notin L$) then $d(S,T)=2$ due to any vertex in $N\setminus S$; but in this case $S$ has no neighbor in $L$.

(iv) If $S\in L$ then $d(S,T)=3$ since the distance from every neighbor of $S$ to $T$ is 2.

Thus we can reconstruct the set $L$ (due to the distance 3 from $T$), and then set of all $S$ such that $v\in S$ but $S\notin L$ (due to the distance 2 from $T$ and non-existence of a neighbor in $L$). Thus we have reconstructed all $S\in V(\Hadw(G))$ containing $v$. Now we can remove all these vertices obtaining the graph $\Hadw(G-\{v\})$ for which the induction assumption is applicable.


$\def\Hadw{\mathop{\rm Hadw}}$If it is not a mauvais ton, I would like to add an easier proof found independently by Sergey Dolgikh and Marat Abdrakhmanov (we used this fact as a contest problem). We assume that $G$ is finite and connected, and again we find all vertices in $H=\Hadw(G)$ corresponding to the vertices of $G$.

Lemma. If $S$ is a vertex of $\Hadw(G)$ with $|S|>1$ and $v\in S$, then $\deg_H S<\deg_H \{v\}$.

Proof. Every neighbor $T$ of $S$ in $H$ can be augmented by a path in $S$ to provide a neighbor $T'$ of $\{v\}$; all these neighbors are distinct since $T'\setminus S=T$. Moreover, $\{v\}$ has some neighbor contained in $S$.

Now, for every $T\in V(H)\setminus\{V(G)\}$ we find its neighbor of maximal degree. By the lemma, this neighbor is a one-vertex set. On the other hand, for every $v\in V(G)$, the set $\{v\}$ is the unique maximal degree neighbor of any component of $G-\{v\}$. Thus we have reconstructed all sets of the form $\{v\}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.