Results 1 to 3 of 3

Math Help - Graph Theory

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    30

    Graph Theory

    Is there a simple graph on n vertices such that the vertices all have distinct degrees? Is there a (general) graph with this property?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    It is not possible to have a simple graph with all distinct degrees.
    It can be proven with the pigeon hole principle.

    For a graph with n vertices:
    Case 1: One vertex has degree 0. This means the degree for vertices range from 0 to n-2, and so 2 of n vertices must have the same degree by pigeon hold principle.

    Case 2: All vertices has degree > 1. This means that degree for vertices range from 1 to n-1, and again 2 of n vertices must have the same degree by pigeon hole principle.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2011
    Posts
    1

    I just started graph theory and lost?

    I understand what a basic graph is and how you find the degree of the graph, but after that I am lost. I need help understanding this question:

    Explain how you would approach the problem described using graph theory. In your discussion, describe how you would model the problem, including what items would be represented by the vertices and edges of a graph and how you would determine how each edge is directed. (You do not have to describe the directedness of each edge.) Also provide an account of your strategy—how you would solve the problem. Then solve the problem and provide the solution, including the values that constitute the sum of entries in the table translating wins to one- and two-stage domination for each player.

    In a round-robin singles pool tournament, each of six competitors plays each other once. The results of the tournament are shown in the following table.

    PlayerDefeatedCarlaRob, Sara, Orlando, MattRobTanya, Orlando, MattTanyaCarla, Sara, MattSaraRob, MattOrlandoTanya, SaraMattOrlando

    Use a directed graph to model this situation and determine a ranking order for the players using one- and two-stage dominance. Then solve the problem and provide the solution, including the values that constitute the sum of entries in the table translating wins to one- and two-stage domination for each player. You don't need to submit the directed graph as a part of your answer


    Any help in how to get started would help. Thank you so much.
    Last edited by NeedingHelp; January 25th 2011 at 04:29 PM. Reason: didnt finish putting the entire question
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 05:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum