Prove that if it is possible to divide the software engineers into two teams

Question

Consider a group of $n$ software engineers working for Orange Computers Ltd; let us call them s1, . . . , sn. Suppose that $s_1$ and $s_2$ hate each other, that $s_2$ and $s_3$ hate each other, that $s_3$ and $s_4$ hate each other, that ..., that $s_{n-1}$ and $s_n$ hate each other, and that $s_n$ and $s_1$ hate each other. Orange Computers Ltd wants to form two teams of software engineers to work on its two mainstream products iPeal and iJuice. Unfortunately placing two software engineers who hate each other in the same team will result in a buggy product.

Prove that if it is possible to divide the software engineers into two teams, such that any two software engineers who hate one another end up on different teams, then $n$ must be even.

My solution is basically if you pick every other person from n people then you would be left with 2 even teams with people who doesn't hate one another. However, I don't know how to rephrase this into an actual proof.

Answer 1

Your idea of the proof is OK, now it's time to formalize it. Let's call the teams we form $T_1$ and $T_2$. They are subsets of $\{s_1,\dots, s_n\}$, and I will make two more assumptions:

1. $T_1\cup T_2 = \{s_1,\dots, s_n\}$
2. $T_1\cap T_2=\emptyset$

Without loss of generality, we can say that $s_1\in T_1$ (otherwise, rename the teams). Now, since $s_1$ and $s_2$ hate each other, we know that $s_2\notin T_1$, but therefore, $s_2\in T_2$. We can now (using induction) prove that:

1. $s_{2k} \in T_2$
2. $s_{2k+1}\in T_1$

which leads to a contraduction if $n$ is odd, since in that case, $s_n\in T_1$ (following rule 1 above) and $s_1\in T_1$ (initial assumption) is not possible since $s_1$ and $s_n$ hate eachother.

Answer 2

Hint: You could write down a graph with the vertices given by the sw engineers $s_1,\ldots,s_n$ and the edges given by ''hating each other''. So there are edges $s_i - s_{i+1}$ for $i=1,\ldots,n$ where $n+1\equiv 1 \mod n$. This graph will provide you with the solution.