# Induced subgraphs of $\text{Exp}(G, K_2)$

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