Let T be a tournament. a) Justify your answers to the following. i) What is the

Question

Let T be a tournament. a) Justify your answers to the following. i) What is the sum of the outdegrees of all the vertices of T? ii) What is the sum of the indegrees of all the vertices of T? b) Use your answers to part a) to develop a conjecture analogous to the First Theorem of Graph Theory for tournaments. Write your conjecture using summation notation. c) Prove your conjecture. d) Do your answers to part a) and your conjecture hold for all digraphs or just tournaments? Justify your answer with a proof or a counterexample.

Explanation / Answer

Let id(v) and od(v) represent the indegrees and outdegrees of a vertex v in the tournament. Now each edge in the underlying graph of the tournament, which is a complete graph by the way, corresponds to exactly one indegree and exactly one outdegree. Let n be the total number of vertices in the tournament. So answer to part (a) is:

id(v) = od(v) = total number of edges in the underlying graph = n(n-1)/2.

I have no idea what is meant by "first theorem of graph theory for tournaments". Leave a comment and there I can answer the remaining parts if required.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.