17.0k views
1 vote
Prove that there is an n-vertex tournament with in-degree equal to out-degree at every vertex if and only if n is odd.

a) Construct an odd-sized tournament with equal in-degrees and out-degrees
b) Use induction to prove the statement
c) Show that an even-sized tournament cannot have equal in-degrees and out-degrees
d) Both a and c

User ManOx
by
7.5k points

1 Answer

1 vote

Final answer:

To prove that there is an n-vertex tournament with in-degree equal to out-degree at every vertex if and only if n is odd, we can construct an odd-sized tournament with equal in-degrees and out-degrees, and also show that an even-sized tournament cannot have equal in-degrees and out-degrees.

Step-by-step explanation:

To prove that there is an n-vertex tournament with in-degree equal to out-degree at every vertex if and only if n is odd, we can follow these steps:

a) Construct an odd-sized tournament with equal in-degrees and out-degrees:

Let's consider a tournament with n vertices, where n is odd. We can assign a directed edge between every pair of distinct vertices. Since every vertex has (n-1) outgoing edges, the out-degree of each vertex is (n-1). Similarly, since every vertex has (n-1) incoming edges, the in-degree of each vertex is also (n-1).

b) Use induction to prove the statement:

We can use mathematical induction to prove that for any odd value of n, there exists an n-vertex tournament with equal in-degrees and out-degrees at every vertex.

c) Show that an even-sized tournament cannot have equal in-degrees and out-degrees:

For an even-sized tournament, let's assume that every vertex has equal in-degrees and out-degrees. However, the sum of in-degrees and out-degrees of all vertices should be even. Since the number of vertices is even, it implies that the sum of all in-degrees and out-degrees would be even, which contradicts the assumption.

d) Both a and c:

Therefore, the correct answer is 'd) Both a and c'.

User Bcb
by
8.5k points

No related questions found

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories