What is the isomorphic graph of k4?

Question

What is the isomorphic graph of a k4 graph? Is every complete graph isomorphic to itself? If there are any theorems related to it, it would be highly appreciated to be pointed out here. Thanks.

Answer 1

Let $G = (V_1, E_1)$ and $H = (V_2, E_2)$. A $\textit{graph homomorphism}$ is a mapping $\varphi: V_1(G) \rightarrow V_2(H)$ such that for vertices $u, v \in V_1(G)$,

$$\lbrace u, v \rbrace \in E_1(G) \implies \lbrace \varphi(u), \varphi(v) \rbrace \in E_2(H).$$

A $\textit{graph isomorphism}$ is simply a bijective graph homomorphism.

Those are the "technical" definitions. Now let's try something a little more intuitive.

I have provided a crudely drawn Geogebra image to help!

Try labelling each of the vertices of $K_4$ with the letters $A, B, C$ and $D$. What we are looking for is a way to map pairs of vertices in $K_4$ to pairs of vertices in another graph $H$ such that the edge structure of the graph is preserved. In the picture I have labelled the vertices of the second graph with $\alpha, \beta, \gamma$ and $\delta$. Let's try the following ($H$ denotes the second graph in the image);

$$\varphi: V(K_4) \rightarrow V(H)$$

such that

$$A \mapsto \alpha$$ $$B \mapsto \beta$$ $$C \mapsto \gamma$$ $$D \mapsto \delta.$$

If you now look at pairs of vertices in $K_4$, do the edges between them line up with the edges in $H$? Take, for example, $\lbrace A, B \rbrace$. Since $A \mapsto \alpha$ and $B \mapsto \beta$, we have that $\lbrace A, B \rbrace \mapsto \lbrace \alpha, \beta \rbrace$. You can try this for the other pairs of vertices in $K_4$ and you will see that the edges line up with the edges in $H$. Can you reverse this process and place each vertex in $H$ onto a vertex in $K_4$ such that the edge structure of $H$ is preserved? If you can, you have a graph which is isomorphic to $K_4$.

Another way to think about it which many people hear is this; can you place the first graph on top of the other graph so that it is completely covered?

For some practice, just draw "any old" graph and try to find some isomorphic graphs.