If $G, H$ are simple, undirected graphs, we define the *exponential graph* $\text{Exp}(G,H)$ to be the following graph:


* the vertex set is the set of all maps $f:V(G)\to V(H)$
* two maps $f\neq g: V(G)\to V(H)$ form an edge if and only if whenever $\{v,w\}\in E(G)$ then $\{f(v), g(w)\}\in E(H)$.


If $G$ is any simple, undirected graph, finite or infinite, is there a graph $G'$ such that $G$ is isomorphic to an [induced subgraph](https://en.wikipedia.org/wiki/Induced_subgraph) of $\text{Exp}(G', K\_2)$?



Induced subgraphs of $\text{Exp}(G, K_2)$
In the sequel we allow $\mathrm{Exp}(\cdot, \cdot)$ to have loops, then the only induced subgraphs of $\mathrm{Exp}(G', K\_2)$ are disjoint unions of isolated vertices, complete graphs with a loop on each vertex (denote such a graph $\overline{K\_n})$ and complete bipartite graphs.


First, consider a non-empty connected simple graph $G'$. For $G'$ with a single vertex we have $\mathrm{Exp}(G', K\_2) = \overline{K\_2}$. For $G'$ with at least two vertices we must have that each vertex of $\mathrm{Exp}(G', K\_2)$ has degree at most one; indeed, consider $f, g, h: V(G') \to V(K\_2)$ such that $g, h$ are neighbours of $f$ in $\mathrm{Exp}(G', K\_2)$. For any $v \in V(G')$ consider an adjacent edge $vu$, we must have $g(v) \neq f(u) \neq h(v)$, hence $g = h$. Thus, $\mathrm{Exp}(G', K\_2)$ consists of isolated vertices, disjoint loops and edges.


For an arbitrary $G'$, $\mathrm{Exp}(G', K\_2)$ is the tensor product of $\mathrm{Exp}(\cdot, K\_2)$ of connected components of $G'$. A tensor product of (disjoint unions of) isolated vertices, loops and edges still consists of isolated vertices, disjoint loops and edges. A tensor product of several copies of $\overline{K\_2}$ is $\overline{K\_{2^n}}$. Finally, a tensor product of $\overline{K\_n}$ with $K\_2$ is $K\_{n, n}$. It follows that all connected components of $\mathrm{Exp}(G, K\_2)$ are isolated vertices, $\overline{K\_n}$ or $K\_{n, n}$.


