I have to prove the following assertion: given a tournament graph with $n$ vertices, $n\geq 5$, there can be made an arrangement of the arcs such that between any two vertices exists at least one way of length at most $2$. Any ideas? Thank you!

  • 6
    $\begingroup$ What have you tried? Where did you get stuck? We want to help you with your specific problems, not just do your (home-)work. However, as it is we don't know what this problem is and thus how to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Dec 8 '14 at 14:51

You asked the question in a little vague way, so let me go over the notions you use. A tournament is a directed graph so that between every two vertices there exists one directed edges. Now, we can thing of the vertices as the numbers $1$, $2$, $\dots,n$. If we direct the edges from $i$ to $j$ whenever $i < j$ then between any two vertices $i$ and $j$ where $i<j$ there is one directed path (what you call "way") of length 1 and unless $j=i+1$ there is one or more paths of length 2. You can start with this example and think what edges to reverse to get the property you want.

(Another more advanced idea would be to look what is happening when you direct the edge between $i$ and $j$ at random. This should work to show what you want, but making this proof works for $n \ge 5$ in a natural way may be very challenging.)

I hope this is helpful.

  • 2
    $\begingroup$ Welcome to CS Stack Exchange, Gil! $\endgroup$ – David Richerby Dec 25 '14 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.