Results 1 to 2 of 2

Math Help - Graph Theory Problem

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Graph Theory Problem

    Prove that every simple graph with at least two vertices has two vertices with the same degree. Is the conclusion true for loopless graphs in general?

    Please help... Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    We will prove a stronger claim : every non-trivial connected component of a simple graph has two vertices of the same degree.

    Let the number of vertices in the component be n. The degree of any vertex within the component has to be at least 1 and at most n-1. Since the number of vertices is 1 more than the number of assignable degrees, by the pigeon hole principle there are at least two vertices that have the same degree.

    The original result easily follows from this, as any graph with at least two vertices that does not have more than one isolated vertex, will have at least one non trivial connected component.

    The result is not true for loopless graphs in general. Consider G = { V={1, 2, 3}, E={(1,3), (2,3), (2,3)} }.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 19th 2011, 02:29 AM
  2. Graph Theory Problem #2
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 20th 2010, 03:44 AM
  3. Graph Theory Problem
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: September 15th 2010, 12:40 AM
  4. Help with Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 2nd 2008, 10:08 PM
  5. Graph theory problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 26th 2007, 11:56 AM

Search Tags


/mathhelpforum @mathhelpforum