Fill This Form To Receive Instant Help

Help in Homework
trustpilot ratings
google ratings


Homework answers / question archive / Show that if two vertices u and v have the same score in a tournament T, then u and v belong to the same strong component of T

Show that if two vertices u and v have the same score in a tournament T, then u and v belong to the same strong component of T

Math

Show that if two vertices u and v have the same score in a tournament T, then u and v belong to the same strong component of T.

Can you explain what does score mean?

Hint : Try to prove it on two lines. Definitely your proof shouldn't be longer than 4 lines! If it is longer, you are doing something wrong.

pur-new-sol

Purchase A New Answer

Custom new solution created by our subject matter experts

GET A QUOTE

Answer Preview

1. Oriented graph: An oriented graph is a directed graph that at most
a single edge exists between two vertices. For example, if u->v is
an edge from u and v, then the edge v->u does not exist in this
graph.
2. Complete graph: any two vertices in the graph must have an edge.
3. Tournament: Tournament is a complete oriented graph.
4. Score: In a tournament with n vertices, each vertex connects with
the other n-1 vertices. So it has k outedges and n-k-1 inedges. The
number k of outedges is called the score of this vertex.

Now we begin our proof.

u and v have the same scores in a tournament. We can assume the tournament
has n vertices and the score of u and v is k. So u and v have k outedges
and n-k-1 inedges.
To show that u and v belong to the same strong components, we only need to
show that there is a path from u to v and there is a path from v to u.
I claim that there is a path from u to v.
If the edge u->v exists, we are done. Otherwise, excluding u and v, there are
n-2 vertices. k of them are those whom u goes to, n-k-1 of them are those who
go to v. But k+(n-k-1)=n-1>n-2, so there must exists some w, such that u goes
to w and w goes to v. So we find the path u->w->v and we are done.
Similarly, there is a path from v to u.

Therefore, u and v belong to the same strong components.

Related Questions