Question

Let G be a round robin tournament graph on n vertices. Consider the matrix representation of G. Prove that the sum of number of 1’s in row j and col j, for any j = 2 ... n,is always n –1.

Answer 1

A round-robin tournament graph is a digraph (directed graph) that is complete (has exactly one edge between each pair of distinct vertices, has no loops).

Example: Let us suppose we have 4 vertices. Then, the complete graph with 4 vertices will be as shown below:

A few examples of possible round robin tournament graphs in this case are:

In case of an undirected graph, the degree of a complete graph with n vertices is n-1, i.e., the number of edges incident on each vertex is n-1, since it is adjacent to each of the other vertices of the graph via exactly one edge.

Now, let us consider a round-robin tournament graph with n vertices. Let us name these vertices 1,2,...,n. Let us consider the vertex named j, such that is arbitrary. Then, j is adjacent to a total of n-1 vertices. Since it is a directed graph, each of these edges goes from one vertex to another. Let us suppose that there are exactly k vertices, such that the edges between them and j are directed towards j. Then, the edges between j and the remaining n-1-k vertices are directed away from j.

<i<n

In the adjacency matrix of this graph,

• the jth column represents the edges directed towards j.
• the jth row represents the edges directed away from j.

Then, the element of the

• ith row and jth column is 1 if there is an edge from i to j.
• ith column and jth row is 1 if there is an edge from j to i.

So, the number of 1s in the

• jth column is the number of edges directed towards j, which is k.
• jth row is the number of edges directed away from j, which is n-1-k.

So, the total number of 1s in the jth row and jth column is the sum of the above two numbers, because the element common to the above row and column, i.e., the element in the jth row and jth column, is 0 (if it wouldn't be 0,it would mean there is an edge from j toi j, i.e., a loop, which is not possible in a round-robin tournament graph).

Total number of 1s in the jth row and jth column = k+(n-1-k) = n-1.

Therefore, sum of number of 1s in row j and column j = $(n-1)\times1$

$=(n-1)$for all j=1,2,3,...,n, and so for all j=2,3,...,n.