Assign integer weights to the edges of Kn. Prove that the total weight on every cycle iseven iff the total weight on every triangle is even.

Solution

1. Sufficient Condition:

• A triangle is a 3-cycle. Thus, if the total weight of every cycle is even, then the total weight of every triangle is also even.

2. Necessary Condition:

• We will use mathematical induction to prove this.

• Steps*:

1. Base Case:

   • For cycles of length 3 (i.e., triangles), we know by assumption that the total weight of every triangle is even.

2. Inductive Hypothesis:

   • Assume that for any cycle of length $k$, the total weight of the cycle is even.

3. Inductive Step:

   • Now, we need to prove that the total weight of any cycle of length $k+1$ is also even.
   • Consider a cycle $C = (v_1, v_2, \dots, v_{k+1}, v_1)$.
   • Insert an edge $(v_1, v_3)$, which splits the cycle $C$ into two parts:
     • The first part is a triangle $T = (v_1, v_2, v_3, v_1)$.
     • The second part is a cycle $C' = (v_1, v_3, v_4, \dots, v_{k+1}, v_1)$, which is a cycle of length $k$.

4. Calculate the Total Weight:

   • By assumption, the total weight of triangle $T$ is even, and by the inductive hypothesis, the total weight of the $k$-cycle $C'$ is also even.
   • Summing the weights of the two parts:
     $$
     (e_{1,2} + e_{2,3} + e_{3,1}) + (e_{1,3} + e_{3,4} + \cdots + e_{k,k+1} + e_{k+1,1}) \equiv 0 \pmod{2}.
     $$
   • Here, $e_{3,1}$ and $e_{1,3}$ refer to the same edge and are counted twice in the total sum.
   • Thus, the final expression becomes:
     $$
     e_{1,2} + e_{2,3} + e_{3,4} + \cdots + e_{k,k+1} + e_{k+1,1} \equiv 0 \pmod{2}.
     $$
   • This shows that the total weight of the cycle $C$ with length $k+1$ is also even.

5. Conclusion:

   • By mathematical induction, the necessary condition holds.