Trusted by Students Everywhere
Why Choose Us?
0% AI Guarantee

Human-written only.

24/7 Support

Anytime, anywhere.

Plagiarism Free

100% Original.

Expert Tutors

Masters & PhDs.

100% Confidential

Your privacy matters.

On-Time Delivery

Never miss a deadline.

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 Sep 02, 2020

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.

Expert Solution

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.

Archived Solution
Unlocked Solution

You have full access to this solution. To save a copy with all formatting and attachments, use the button below.

Already a member? Sign In
Important Note: This solution is from our archive and has been purchased by others. Submitting it as-is may trigger plagiarism detection. Use it for reference only.

For ready-to-submit work, please order a fresh solution below.

Or get 100% fresh solution
Get Custom Quote
Secure Payment