0

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

Robo Jumble
  • 93
  • 1
    Try to avoid abuse of notation like $$|V_1|=3,3,2,2$$ Forst, $|V_1|=4.$ And this sequence isn’t a property of $V_1,$ it is a property of $G_1=(V_1,E_1).$ Instead, write the two line like: $$(V_1,E_1): 3,3,2,2$$ or $$G_1: 3,3,2,2$$ – Thomas Andrews May 17 '21 at 15:10
  • 2
    Re: "It's not sufficient to use degree sequence to show they are isomorphic" Compare the two graphs... the first of which consisting of a triangle and a pentagon (a disjoint $C_3$ and a $C_5$) versus the second graph consisting of two squares (two disjoint copies of $C_4$). Both of these graphs have the same number of vertices, same number of edges, same degree sequence $2,2,2,2,2,2,2,2$ and a number of other properties and yet are not isomorphic. The first is not bipartite for instance while the second is. – JMoravitz May 17 '21 at 15:13
  • are the two graphs not isomorphic ? – Robo Jumble May 17 '21 at 17:01

1 Answers1

3

Comparing properties can show that two graphs are not isomorphic. but cannot reliably be used to show graphs are isomorphic. Consider these two:

drawing of the graph <span class=$(\{a,b,c,d,e,f\},\{\{a,b\},\{b,c\},\{c,d\},\{d,e\},\{d,f\}\})$" />

drawing of the graph <span class=$(\{1,2,3,4,5,6\},\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{3,6\}\})$" />

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:

  • $G$ is a bijection from $V_1$ to $V_2$, and
  • for all $x$ and $y$ in $V_1$, $(x \sim y) \iff G(x) \sim G(y)$.

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.

Matthew Leingang
  • 26,112