2
$\begingroup$

I want to find another graph that has 6 vertices and each has degree $3$ that is not isomorphic to these two graphs below. I know that these two graphs are isomorphic. They will all have the same degree sequence, So I kind of stuck how to find such graph. Any suggestions ?

enter image description here

$\endgroup$

4 Answers 4

2
$\begingroup$

Draw two triangles and join them with a 1-factor.

$\endgroup$
6
  • $\begingroup$ What do you mean, join them with a 1-factor ? $\endgroup$
    – alkabary
    Commented Oct 29, 2015 at 16:38
  • 1
    $\begingroup$ 1-factor is a perfect matching. Choose a vertex from the first triangle and join it with a vertex from the second triangle. After that choose a second vertex from the first triangle and join it to another vertex from the second triangle, and so on. If you do not want to get vertex with degree 4 or 5, then you can do this uniquely up to isomorphisms. $\endgroup$ Commented Oct 29, 2015 at 16:42
  • $\begingroup$ Ok I got this, Now Why is this graph not isomorphic to the other two graphs ? $\endgroup$
    – alkabary
    Commented Oct 29, 2015 at 16:49
  • $\begingroup$ because this graph contains a triangle, while yours does not. $\endgroup$ Commented Oct 29, 2015 at 16:52
  • $\begingroup$ But what makes it not isomorphic still, Like what makes the triangle showing up in this graph not isomorphic ? $\endgroup$
    – alkabary
    Commented Oct 29, 2015 at 16:54
2
$\begingroup$

A graph on $6$ vertices is regular of degree $3$ if and only if its complement is regular of degree $2.$

First find two nonisomorphic $2$-regular graphs on $6$ vertices (hint: one is connected, the other is not); their complements will be nonisomorphic $3$-regular graphs on $6$ vertices.

$\endgroup$
0
$\begingroup$

This graph being $3-regular$ on $6$ vertices always contain exactly $9$ edges.

One possible graph is as follows:

-Join the vertices $1,2,3,4,5,6$ by making parallel edges between each pair $1$ & $2$, $3$ & $4$, and $5$ & $6$. This will exhaust $6$ of your edges. Now join each pair $2$ & $3$, $4$ & $5$, $6$ & $1$ by using $3$ more edges. -

As this graph is not simple hence cannot be isomorphic to any graph you have given.

$\endgroup$
0
$\begingroup$

The Stefan Gyürki's answer and the author's one can solve one variant of this question. If we change the question to be more specific, we can find one nonisomorphic graph based on more conditions to use.

Find the number of nonisomorphic simple graphs with six vertices in which each vertex has degree three.

This is shown in this lecture p2. Here I give some notes for this doc.

  1. Since the lecture doesn't consider the case where the vertices are splitted into 3 pairs and each pair are connected with one endpoint has one loop, here it probably assumes the 3-regular graph is one simple graph, although it is not always this case.
  2. Since this is one unlabelled vertex problem, so we can assume

    Let x be any vertex of such 3-regular graph and a, b, c be its three neighbors.

  3. It is splitted into 2 cases (whether $y,z$ are adjacent or not), so it will consider all possible cases.
    1. "If y and z are not adjacent", based on the assumption of the specific question, loops are excluded. So only the bipartite is possible.
    2. "By symmetry" is due to the assumption of "unlabelled vertex problem".

we can also use the bof's answer to solve the above specific variant.

Based on this, if we exclude all loops (then only 1-(i),2-(i,ii),3-(i) are left) and all parallel edges (then only 1-(i),2-(i) are left), then we has only 2 graphs. This is same as the above method.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .