# Graph with degree sequence (3,3,3,3,3,3)

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?

• RandomGraph[DegreeGraphDistribution[{3,3,3,3,3,3}]] can be used to generate samples. – Sasha Apr 2 '13 at 23:11

                 *
/|\
/ | \
*  *  *
\ | /
\|/
*


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.

Consider the vertices and edges of a triangular prism.

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: