what makes a digraph transitive?

1.2k Views Asked by At

Draw a digraph of a transitive tournament on 5 teams.

What i drew was a pentagon and a star in the middle and made it transitive but doesn't that just contradicts the winning team? like 1 beat 2 , 2 beat 3 etc meaning 1 beats itself?

1

There are 1 best solutions below

4
On BEST ANSWER

In order for your graph to be transitive, it must be possible to number the vertices $1,2,3,4$, and $5$ in such a way that if $1\le k<\ell\le 5$, the edge between vertex $k$ and vertex $\ell$ is directed from $k$ to $\ell$. If you can do that, your graph is correct. There is no circularity: $1$ beats $2$, $2$ beats $3$, $3$ beats $4$, and $4$ beats $5$, but $5$ loses to everyone else, and no one beats $1$. $1$ is the winner; $2$ beats everyone except $1$; $3$ beats everyone except $1$ and $2$; $4$ beats only $5$; and $5$ loses to everyone else.