Show that for $2$ vertices $u$ and $v$ have the same score in a tournament $T$ then $u$ and $v $ belong to the same strong component of order $k$

337 Views Asked by At

a) Show that for $2$ vertices $u$ and $v$ have the same score in a tournament $T$ then $u$ and $v $ belong to the same strong component of order $k$

b) Prove that every regular tournament is strong

Define the relation on $V(T)$ by $u$ is related to $v$ if there is both $u-v$ path and $v-u$ path in $T$. This is an equivalent relation so this relation partition $V(T)$ into equivalent classes $V_1, V_2,..., V_k$ $(k\geq 1)$. Let $S_i= T[V_i]$ for $1 \leq i \leq k$, then $S_i$ are called strong components of $T$

a)

From $u$ and $v$ have the same score I can see that $od(u)=od(v)$. So there is a path from $u$ and $v$ to other $k$ vertices, but how do I know there is a path from $u$ to $v$ and from $v$ to $u$ from these info?

b)

Let $T$ be a regular tournament then for every $v$ in $T$ , $id(v)=od(v)$. A tournament is a directed graph, and a directed graph such that for every $v$ in $T$ , $id(v)=od(v)$ is Eulerian. So a regular tournament is strong because it contain an Eulerian cycle.

1

There are 1 best solutions below

5
On BEST ANSWER

Proof of part a:

By symmetry we may assume that the arrow between $u$ and $v$ is directed $uv$. Not counting any other arrows we see that $u$ is ahead in outdegree, so $v$ needs to have at least one arrow to a vertex $w$ such that $uw$ is not an arrow. But then $wu$ is an arrow and $vwu$ is a directed path from $v$ to $u$.

The proof of part b looks fine.