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



Isomorphic Hadwiger graphs
$\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.


