Isomorphic Hadwiger graphs

Question

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$?

Answer 1

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

Answer 2

$\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\}$.