Question

Let \(T\) be a tournament on \(n\) vertices. If \(\Sigma\) denotes a summation over all the vertices of \(T\), prove that \(\sum\) outdeg \((\dot{v})^{2}=\Sigma \operatorname{indeg}(\boldsymbol{v})^{2}\).

Short answer

The equality \(\Sigma\) outdeg \(\boldsymbol{v}\)² = \(\Sigma\) indeg \(\boldsymbol{v}\)² holds for a tournament on n vertices, because each is the total number of pairs of arrows having the same initial or terminal vertex, respectively. Both refer to the total number of 2-cycles in the tournament graph.

Step-by-step solution

Interpret Given Information

We have been given that T is a tournament on n vertices, meaning that for any two distinct vertices, there is exactly one directed edge between them. Also, we are asked to prove an equality dealing with the sum of the squares of the vertices' indegrees and outdegrees.

Apply Handshaking Lemma

From the Handshaking Lemma, we know that the sum of the degrees of all vertices in a graph equals twice of its edges. Here, in a tournament, every two vertices are connected by one arrow, thus the total edge is \(n(n-1)/2\). Each arrow contributes one to the outdegree of one vertex and the indegree of another. So, \(\Sigma\) outdeg \(\boldsymbol{v}\) = \(\Sigma\) indeg \(\boldsymbol{v}\) = \(n(n-1)/2\).

Double Counting

The left hand-side of the equation can be expressed as the total number of pairs of arrows having the same initial vertex. Similarly, the right hand-side of the equation can be expressed as the total number of pairs of arrows having the same terminal vertex. Since each pair of arrows corresponds to a 2-cycle (consisting of a pair of two edges with opposite directions), these two quantities are equal.

Key concepts

Understanding the Handshaking Lemma

The Handshaking Lemma is a fundamental concept in graph theory. Imagine a party where every guest shakes hands with each other; the lemma states that the total number of handshakes will be even. Why is this relevant in graph theory? Because when we represent each handshake as an edge in a graph and each guest as a vertex, the lemma helps us understand that the sum of degrees (the number of edges connected) of all vertices is twice the number of edges in the graph.

In the context of a tournament graph, which is a directed graph (digraph), the Handshaking Lemma still applies but with a slight twist. Instead of looking at total degrees, we look at the sum of indegrees (the number of edges coming into a vertex) and outdegrees (the number of edges going out from a vertex). Each match in a tournament graph can be thought of as a directed handshake, meaning each game has a winner and a loser. The lemma in this scenario ensures that the sum of indegrees and outdegrees across all the vertices equals the total number of matches, which for a complete tournament is (n-1)/2. It's this beautiful balance that lets us delve into more specific equalities, like the one our exercise is exploring.

Indegree and Outdegree in Tournament Graphs

In a tournament graph—which embodies a competition where each player or team competes against each other exactly once—the concepts of indegree and outdegree become quite intuitive. The indegree of a vertex is the number of matches a player has lost, whereas the outdegree represents the number of matches won. Since every possible pairing of players results in one win and one loss, each encounter contributes to both an indegree and an outdegree across the tournament graph.

In this way, the indegree and outdegree distributions across all vertices carry detailed information about the outcomes of the competition. When we look at the summation of outdegrees and indegrees squared, as in our exercise, we’re essentially examining a deeper layer of this distribution - not just how many wins or losses each player has, but the spread and concentration of these across all players.

Double Counting Argument in Proofs

A double counting argument is an elegant and often-used tool in combinatorial proofs. It involves counting the same quantity in two different ways to reveal a hidden relationship or equality. Think of it like finding two different paths to the same destination. In tournament graphs, this approach is especially powerful.

When we apply a double counting argument to our exercise, we’re essentially saying that each match-up can be viewed from the perspective of wins or losses - and therefore, outdegrees or indegrees - yet when compiled together in a certain way, the totals should reflect the same reality. For the sums of the squares of the outdegrees and indegrees to be equal, it implies a symmetry in the distribution of match outcomes that is innate to the structure of a tournament graph. Each game that increases the outdegree of one vertex, thus increasing one side of our equation, also increases the indegree of another vertex, balancing the other side of the equation.