Results 1 to 2 of 2

Math Help - Proof help need graph theory - Please !

  1. #1
    Newbie
    Joined
    Mar 2012
    From
    home
    Posts
    2

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2008
    Posts
    1,035
    Thanks
    49

    Re: Proof help need graph theory - Please !

    Quote Originally Posted by sexychessbabe View Post
    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.
    Last edited by tom@ballooncalculus; March 24th 2012 at 08:25 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 12th 2010, 12:00 AM
  2. Graph theory proof
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: May 6th 2010, 06:27 AM
  3. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 5th 2010, 09:34 AM
  4. Graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 26th 2009, 10:01 PM
  5. Graph Theory Proof please:-
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 18th 2008, 04:06 PM

Search Tags


/mathhelpforum @mathhelpforum