Question

A round-robin tournament is an event wherein every competing team plays every other team once and only once. Assuming no ties, every game can be depicted on a graph G using a directed edge (x, y), where team x has defeated team y.

(a) Assuming n teams participate in a round-robin tournament, how many vertices and edges will graph G depicting the tournament have?

(b) Is it preferable to be a source or a sink in graph G?

(c) Can G have multiple sources and/or sinks? Explain why or why not.

(d) Assuming G has a cycle, can it have a sink? Explain why or why not.

Answer 1

Solution :

(a)

Suppose that n teams participate in the round-robin tournament.
Since every vertex corresponds to a team, hence the number of vertices of the graph G is n.
Since every pair of distinct vertices of G is connected by a unique edge (every team plays every other team once and only once and there are no ties), hence the number of edges of G is ⁿC₂ = n(n-1)/2.


(b)

By definition, a source is a vertex v in G such that there is no edge that terminates at v.
By definition, a sink is a vertex w in G such that there is no edge that starts at v.

Now, if team x defeats team y, then the edge joining vertex x to vertex y in G is directed from x to y.

Therefore, a source in G represents a team T such that there is no edge that ends at T, or equivalently, a source in G represents a team T which defeats all other teams.

Similarly, a sink in G represents a team T such that there is no edge in G that starts at T, or equivalently, a sink in G represents a team T which is defeated by all other teams.

Therefore, it is preferable to be a source in graph G (a team which defeats all other teams).


(c)

No. G cannot have multiple sources and/or sinks.

Suppose that G has two sources v and w. Then, using the fact that v is a source, it follows that the unique edge joining v and w is the directed edge (v,w) (v defeats w).
Again, using the fact that w is a source, it follows that the unique edge joining v and w is the directed edge (w,v) (w defeats v).
Thus (v,w) = (w,v) (by uniqueness of the edge joining v and w). This is a contradiction as v and w are distinct.

Hence, G cannot have two sources. Using the analgous argument for sinks, it follows that G cannot have multiple sinks.


(d)

Yes. G can have a sink.

As an example, suppose that there are 4 teams x,y,z and w participating in the round-robin tournament.
Then, G has 4 vertices x,y,z and w.
Consider the following directed edge set of G given by, E = { (x,y) , (y,z) , (z,x) , (x,w) , (y,w) , (z,w) }.

It is clear that the above directed graph G has a cycle formed by vertices x,y and z.
At the same time, G has w as a sink.
This is better depicted in the following diagram :

Y w z SINK