Thread: Proof help need graph theory - Please !

Prove that for any integer n>=5 there exists a graph with n vertices all of which have degree 4.

How do I prove this? I assume by induction with n=5 as the initial step (easy using Havel-Hakimi), then assume works for n, show works for n+1, but it gets messy. Can you show me the induction or have any other method to prove this?

Thanks.
SCB

Originally Posted by sexychessbabe

show works for n+1, but it gets messy

Why messy? I'm looking at my regular degree-4 graph with n=5. I choose any two non-adjacent edges and replace with 4 edges from vertex number 6. And again.

I.e., pull the two non-adjacent edges together until they touch, creating a new vertex and becoming 4.