Hey so I am having trouble with these two questions. I feel like I could use induction here but am not sure how (still very new to graph theory).

For part A I think proving the base case is easy using K_4. For n > 4 then I can use the fact that n is even to split it into two subgraphs of size m such that n = 2m, and then connect vertices in such a way that each have degree 3. Again, not sure how to use induction here, if its even necessary.

For part B I have created an algorithm sort that can generate these graphs, but I do not know how to turn it into a proof. This is what I have (in orange) (sorry for the messiness):



This creates graphs with degree sequence (3,3,...,3,1).

Can anyone help? Thank you!

a) Just draw it !

Let V1 ... Vn the vertices, with n even : n=2p

Draw a rectangle with length p and width 1, put your vertices along the length of the rectangle.
Now connect each vertex to the one opposite to it (on the other length).
Every vertex in the interior of both length will have degree 3.
Only the vertices on the 4 corners have degree 2 : connect them, and you're good.

b ) I've got it !
Your orange drawing IS a proof !

This post was edited by feanur on Sep 15 2015 10:52pm

Great, thanks! I wasn't sure if just drawing graphs was formal/rigorous enough for proofs in graph theory so its good to know they are

Nice job, all you needed is existence, so finding a way to generate it for arbitrary n=2k+1 is cool