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.
[Math] the isomorphic graph of k4?
graph theorygraph-isomorphism
Related Solutions
In simple terms, two graphs are isomorphic to each other so long as there is a bijection between the two vertex sets and such that the bijection preserves edges. That is, two graphs $G$ and $G'$ are isomorphic if there exists a bijection, $\phi: V(G) \to V(G')$, and if that bijection also preserves edges. Explicitly, this means that if $uv$ is an edge in $E(G)$, then $\phi (u) \phi (v)$ is an edge in $E(G')$.
One can visualize a graph isomorphism in two ways. 1. Start with a graph and move around vertices in what ever way you want while keeping all the edges in tact. The result, a graph that looks different, but isn't really. 2. A re-labeling of the vertices of $G$. This produces a graph that looks the same, but the vertices are called something else.
Automorphisms are a little bit trickier. The way I look at an automorphism is a moving around of vertices (while keeping edges in tact, as in (1) above) with the caveat that the graph must look exactly the same as before. For example, take $C_4$ with vertex set $V(G) = u_1,u_2,u_3,u_4$ and edge set $E(G) = u_1u_2,u_2u_3,u_3u_4,u_4u_1$ and consider the following bijection.
1. $\phi: V(G) \to V(G')$ where $\phi$ is the permuation $(u_1u_2u_3u_4)$ that sends $u_1 \to u_2$ $u_2 \to u_3$ $u_3 \to u_4$, and $u_4 \to u_1$. (If one is unfamiliar with cycle notation). This is an isomorphism since every edge is preserved, and indeed it is also an automorphism since the resulting graph looks exactly the same as the regular graph. (the permuation above is really just a rotation by 90 degrees if you lay out the original as a "square", as is tradition.
As the above labeling shows, the two graphs are isomorphic. Once you have it in your mind that it's possible, it's simple to do. Just pick a 5-cycle, label those vertices A through E, and then the remaining vertex adjacent to A not on that cycle has to be F and so on to the end.
A bunch of years ago, I wrote a proof that there was only one graph up to isomorphism (i.e. the Petersen graph) on ten vertices that was 3-regular and had a diameter of 2. I can post that as well if you are interested.
Best Answer
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.