Thread: 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?

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.

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.