Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

Test the following sequences using to see if they are graphical or not: (if they are graphical draw an exemplar graph having that valency sequence)

share|improve this question
1  
The title and the question don’t agree; are you interested in finding one such graph, or in finding all of them? – Brian M. Scott May 31 '12 at 11:34
What following sequences? Can you do something so the title and the body agree, and make sense? – Gerry Myerson May 31 '12 at 11:35
5  
Perhaps you should start by considering the vertex of degree 4. Draw it and the 4 neighbors. What can you do next? – John Engbers May 31 '12 at 11:38

1 Answer

up vote 3 down vote

There is an algorithm to easily verify valency sequences.

Enumering all possible graphs is a slightly more difficult problem. As there are only a few graphs with 6 nodes you can however figure out that there are only 2 possible graphs with that sequence: (you can modify the algorithm to give you all possible graphs)

Graphs 1 and 2:

enter image description here

share|improve this answer
2  
Thanks for finding that page that I created back in 2003, I forgot I ever did it! This year I was teaching my course again and this time I made up a Maple worksheet (using the GraphTheory package which is available since Maple 13). It makes a list of all simple graphs with any given valency sequence, and is available here: faculty.capebretonu.ca/jpreen/410112w1.mws – jp26 Jun 1 '12 at 15:50
@jp26 neat to see that you are using stackexchange too. I found your description of the algorithm very straight forward and easy to understand, so I linked it. – Listing Jun 1 '12 at 20:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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