For both of these degree sequences have an even sum and they both have an even number of odd degree vertices. This is the only criteria I have learned for these problems for such graphs to exist. So the first one by this could potentially exist but it logically doesn't make sense because if you start with a degree 5 vertex and leave two of the connected vertices with degree one the we have six vertices there is no way to create the remaining degrees without increasing these other degrees right? To create a degree four vertex we have 3 free vertices to build off of but this would need to connect to one of the already established vertices. For the second sequence I think I have drawn a picture which satisfies the degree requirements with 7 vertices and 8 edges but this is simply through trial and error. Is there a way to formally prove that this graph exists and create it without having to just draw pictures until something works/doesn't work?
Asked
Active
Viewed 404 times
1
-
1the gist is that there are some good algorithms and theoretic results about existence: Havel-Hakimi algorithm and Erdös Gallai theorem – Badam Baplan Dec 07 '17 at 04:04
-
1Try this theorem: https://math.stackexchange.com/questions/61361/what-condition-need-to-be-imposed-on-havel-hakimi-theorem-to-check-for-connected – Caleb Stanford Dec 07 '17 at 04:04
-
Thanks! That is useful to me but is that the only method? The class I’m in is quite elementary and will not cover any algorithmic aspects of graph theory. – Corey Dec 07 '17 at 04:10
-
@Corey - You've basically followed the Haval-Hakimi algorithm for your first example : 1) Take the vertex with highest degree (d), 2) connect it to the next d vertices, ordered by degree, 3) repeat until you have a graph, or cannot go further (roughly!) – gilleain Dec 07 '17 at 13:02
-
As you found, if you don't have enough vertices left to connect to, then you can conclude that there is no such graph. Also, if any of the degrees become negative, then you also terminate. – gilleain Dec 07 '17 at 13:04