graph theory - why don't this graph exist?

104 Views Asked by At

Consider a tournament graph on $n$ nodes. Why does a graph with the following property not exist? Two nodes have the same outdegree and the other $n-2$ nodes have different outdegrees.

1

There are 1 best solutions below

0
On

If your graph has two vertices of outdegree $k$ and no vertex of outdegree $t$, the sum of all outdegrees is $k+(0+1+\ldots+(n-1)-t)$. This sum is $0+\ldots+(n-1)$ for any tournament, so that $k=t$, a contradiction.