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?
Re: Proof help need graph theory - Please !
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.
Originally Posted by sexychessbabe
I.e., pull the two non-adjacent edges together until they touch, creating a new vertex and becoming 4.