2
$\begingroup$

Does there exist a graph with degree sequence (3,3,3,3,3,3)? I am pretty such graph does not exist since I have tried to draw one without success, but is there a way to prove it?

$\endgroup$
  • $\begingroup$ RandomGraph[DegreeGraphDistribution[{3,3,3,3,3,3}]] can be used to generate samples. $\endgroup$ – Sasha Apr 2 '13 at 23:11
12
$\begingroup$
                 *  
                /|\  
               / | \  
              *  *  *  
               \ | /  
                \|/  
                 *

Now connect one more vertex to the three on the horizontal midline.

By the way, the Erdős-Gallai theorem gives you a way to determine whether any given degree sequence can be realized in a simple graph.

| cite | improve this answer | |
$\endgroup$
8
$\begingroup$

Consider the vertices and edges of a triangular prism.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

The two non-isomorphic graphs with these degree sequences can be generated using geng which comes with nauty. The command is

geng 6 9:9 -d3 -D3

where we have 6 vertices, 9:9 means between 9 and 9 edges, -d3 means minimum degree 3 and -D3 means maximum degree 3. These can be viewed using showg, but I prefer to write my own script to draw them:

The two $3$-regular graphs on $6$ vertices

| cite | improve this answer | |
$\endgroup$

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.