7
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ You might look at "theta graphs". They look like the letter theta, consisting of three paths between the same two points. $\endgroup$ – Lord Shark the Unknown Apr 15 '17 at 6:17
  • $\begingroup$ If two graphs have the same degree sequence, can you think of some properties in which they must differ for them not to be isomorphic? $\endgroup$ – PJK Apr 15 '17 at 6:32
  • $\begingroup$ No, I don't think so $\endgroup$ – Just a girl Apr 15 '17 at 6:36
  • $\begingroup$ So, there is not any? $\endgroup$ – Just a girl Apr 15 '17 at 6:36
  • $\begingroup$ There is. They can have simple circuits of different length. $\endgroup$ – PJK Apr 15 '17 at 6:37
2
$\begingroup$

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!)$.

enter image description here

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! I have a question, how could you tell that such graphs exist? $\endgroup$ – Just a girl Apr 15 '17 at 6:42
  • $\begingroup$ I mean, given a degree sequence, how do you know that you can make a 2 non isomorphic graphs with that sequence? $\endgroup$ – Just a girl Apr 15 '17 at 6:44
  • $\begingroup$ @Just a girl I don't know any criterions that prove it is possible. I just visualized some graphs and worked out two examples. Proving such a thing is not possible usually involves supposing two graphs have that degree sequence and then constructing the isomorphism. $\endgroup$ – Stella Biderman Apr 15 '17 at 12:51
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @bof: You're absolutely right. I though simple only meant no loops. I'll fix my post. $\endgroup$ – Jaap Scherphuis Sep 12 '17 at 15:48
  • $\begingroup$ Good, but I'd suggest using some alternative to "simplified". "Reduced", maybe? I don't know if there's a standard term for the result of removing vertices of degree 2, but there's something funny about calling it a "simplified" graph when you have turned a simple graph into a non-simple graph! $\endgroup$ – bof Sep 12 '17 at 21:31
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! I have a question, given a degree sequence, how can you tell if there exists two graphs that are non isomorphic with those degrees? $\endgroup$ – Just a girl Apr 15 '17 at 6:53
  • $\begingroup$ Its not like there is a definite rule but as I said above, we have to look for a property, which if different for two graphs, makes impossible for them to be isomorphic. Having simple circuits of different length is one such property. $\endgroup$ – PJK Apr 15 '17 at 7:00
  • 1
    $\begingroup$ @ Just a girl if the degree sequence is like (x,x,x,x,x) mean each node has same degree then definitely there is a unique graph upto isomorphism (easy case). $\endgroup$ – user275490 Apr 15 '17 at 7:29
  • $\begingroup$ second case if the the degree of each vertex or node is different except two then also there is one graph upto isomorphism. For more read about rigid graphs. $\endgroup$ – user275490 Apr 15 '17 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.