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$

3 Answers 3

Reset to default
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
    Oct 29, 2015 at 16:38
  • $\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$
    – Stefan Gyürki
    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
    Oct 29, 2015 at 16:49
  • $\begingroup$ because this graph contains a triangle, while yours does not. $\endgroup$
    – Stefan Gyürki
    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
    Oct 29, 2015 at 16:54
1
$\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$

You must log in to answer this question.

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