Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Are there simple graphs $G$ and $H$ both with vertex degrees $2,2,2,2,3,3$ such that $G$ and $H$ are NOT isomorphic? if so, draw them, otherwise, explain why they don't exist.
I'm having trouble answering this question. I know that this sequence is graphical, but how can I know how many are there that are not isomorphic and how to draw them. Can someone please help?
Thank you!
Yes, there are. I'll describe two such graphs.
First, arrange the six vertices in a 2 by 3 grid. Then connect vertices so as to form the number $8$ as seen on sports scoreboards or some digital clocks. This is what a commenter refers to as a theta graph.
For the second example, call the vertices of degree $3$ $A$ and $B$ and the other four $x,y,z,w$. Set $A$ adjacent to $x,y,z$, $B$ adjacent to $x,y,w$, and $z$ adjacent to $w$.
In the first example, the degree $3$ vertices are adjacent but in the second they are not, so the two graphs are non-isomorphic.
Vertices of degree 2 are fairly uninteresting as they can be removed from a graph by combining its two edges into one.
Suppose you did that to your graph(s), then you would be left with a graph with two vertices of degree 3. There are only two such reduced graphs: Either all the edges connect the two vertices, or they are connected by only one edge and both have a single loop.
Now insert the four degree-2 vertices back again.
Case 1: The reduced graph has three edges connecting the two nodes.
You can distribute the degree-2 vertices over the three edges in several distinct ways. As the three edges of the reduced graph are equivalent, all that matters is how you split the four added vertices into three groups (some of which may have zero vertices). There are four ways to do this: 0+0+4, 0+1+3, 0+2+2, or 1+1+2. This gives four non-isomorphic graphs. Note however that the 0+0+4 graph is not simple, because of the two 0 edges. So this gives 3 simple graphs.
Case 2: The reduced graph has one edge connecting the two vertices, and two loops, one on each vertex.
Each of the loops needs to have at least two degree-2 vertices added, because otherwise the graph will be not simple. We only have 4 vertices available so each loop must have exactly two vertices added. This gives the fourth simple graph.
Draw two hexagons. On one, draw a chord that bisects it and in another, draw a chord that does not. Then you get two nonisomorphic graphs because one has a simple circuit of length $4$ and the other does not.
Yes, it is possible see the image below and they are not isomorphic to each other because second graph contain a cycle of length 3 (4-5-6-4), where as first graph does not have a cycle of length 3.
Number of non isomorphic graphs = Total number of graphs with the given degree sequence - total number of isomorphic graphs $(4! \times 2!)$.
There are 4 graphs whose degree sequence is "2, 2, 2, 2, 3, 3" and which are not isomorphic in pairs.
