Let G be the graph with vertex and edge sets $$V = \{1, 2, 3, 4\}$$ and $$E = \{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\}\}$$
and H be the graph with vertex and edge sets
$$V = \{a, b, c, d\} $$and $$E = \{\{a,b\},\{a,d\},\{b,c\},\{a,c\},\{c,d\}\}$$ Question is "write down an isomorphism between them?" i have chosen the following
$$ϕ(1)=a$$ $$ϕ(2)=c$$ $$ϕ(3)=b$$ $$ϕ(4)=d$$ Number of edges $$|E_1|=|E_2|=5$$ Degree sequence for $$|V_1|=3,3,2,2$$ $$|V_2|=3,2,3,2$$
$$ϕ(\{1,2\})=\{a,c\},ϕ(\{1,3\})=\{a,b\},ϕ(\{1,4\})=\{a,d\},ϕ(\{2,3\})=\{c,b\},$$
$$ϕ(\{2,4\})=\{c,d\}$$ therefore they are isomorphic is my method correct is there a better way to show it?
Also how do you figure the number of isomorphism two graphs have between them
Any type of help will be much appreciated
Comparing properties can show that two graphs are not isomorphic. but cannot reliably be used to show graphs are isomorphic. Consider these two:
These two graphs have the same number of vertices (6) and edges (5), and the same degree sequences ($3,2,2,1,1,1$), but are not isomorphic. The first graph's degree 3 vertex has two neighbors with degree 1, but the second graph's degree 3 vertex has two neighbors with degree 2.
To show that graphs are isomorphic, you most often need to exhibit an isomorphism. You gave a function $G$ from $V_1$ to $V_2$. You need to show:
There are many ways to show a function is a bijection. Since $G$ is a function from one finite set to another of the same size, it's sufficient to show that $G$ is injective.
Since $|V_1| = 4$, there are $\binom{4}{2}=6$ sets of distinct vertices $x$ and $y$. You can just write down all of them and check if adjacent vertices in the first graph are sent by $G$ to adjacent vertices in the second graph.