Results 1 to 5 of 5

Math Help - Regular Graphs

  1. #1
    Junior Member
    Joined
    Apr 2008
    Posts
    56

    Smile Regular Graphs

    Let G be an r-regular graph with n verticies and m edges. Find (& prove) a simple algebraic relation between r, n, & m.

    Definition: r-Regular - all verticies have degree r.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by ccdelia7 View Post
    Let G be an r-regular graph with n verticies and m edges. Find (& prove) a simple algebraic relation between r, n, & m.

    Definition: r-Regular - all verticies have degree r.
    A good place to start is that every edge increases the degree of two vertices by 1. That being the case, if the graph is r-regular, there must be an even number of edges. Let's examine cases where n = 4.

    You could have r = 1, in which case there would be two edges (m = 2)
    You could have r = 2, in which case there would be four edges (m = 4)
    You could have r = 3, in which case there would be six edges (m = 6)

    So it looks like the relationship is rn = 2m. Try it and you will see that it works for larger graphs as well. The proof hinges on the fact that every edge increases the degree of two vertices by 1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2008
    Posts
    56

    Smile

    Does it really work for r=1 - I would think there would be one edge in that case. Maybe I'm not looking at it right??
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Apr 2008
    Posts
    56

    Smile

    Got it! you're right!! I was thinking differently for n verticies!! Thanks iceman!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    That answer seems to apply only to simple graphs. (See my other reply.)
    It does not apply if by graph you mean that loops and multiple edges are allowed.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pairwise non-isomorphic regular graphs!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 29th 2009, 12:22 PM
  2. [SOLVED] Non-isomorphic regular graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 28th 2009, 03:19 PM
  3. Are all regular graphs isomorphic?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 25th 2009, 08:29 AM
  4. k-regular graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 5th 2009, 02:08 AM
  5. Hamiltonian regular graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 8th 2006, 08:41 PM

Search Tags


/mathhelpforum @mathhelpforum