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

Answer: (a) In the graph (directed) of a round-robin tournament, each vertex is connected to every other vertex by a directed edge thereby forming a complete graph on n vertices. Hence there will be total of n vertices and edges will be

(b) If team A (say) remains undefeated in the tournament then there will be no edge terminating at A and hence it will be source vertex.

Further if team B doesn't manage to win a single game then there will be no edge originatig from B and hence it will be sink vertex.

Depending on the outcomes of games, the graph for a round-robin tournament may have the possibility of source and sink.

(c) G canot have multiple sources /sinks. If and are two sources in G then

This implies that team   wins from every team participating in the tournament which leads to contradiction that that team is undefeated.

Hence there cannot be multiple sources/sinks in G.

(d) If G has a cycle consisting of veftices then G cannot have a sinkbecause in a cycle every vertex has

so cannot be a sink.

Further, if G has a cycle consisting of vertices then G may have a sink because there may exist a vertex not belonging to the cycle such that