728x90
반응형
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*:
Base Case:
- For cycles of length 3 (i.e., triangles), we know by assumption that the total weight of every triangle is even.
Inductive Hypothesis:
- Assume that for any cycle of length k, the total weight of the cycle is even.
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=(v1,v2,…,vk+1,v1).
- Insert an edge (v1,v3), which splits the cycle C into two parts:
- The first part is a triangle T=(v1,v2,v3,v1).
- The second part is a cycle C′=(v1,v3,v4,…,vk+1,v1), which is a cycle of length k.
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:
(e1,2+e2,3+e3,1)+(e1,3+e3,4+⋯+ek,k+1+ek+1,1)≡0(mod2). - Here, e3,1 and e1,3 refer to the same edge and are counted twice in the total sum.
- Thus, the final expression becomes:
e1,2+e2,3+e3,4+⋯+ek,k+1+ek+1,1≡0(mod2). - This shows that the total weight of the cycle C with length k+1 is also even.
Conclusion:
- By mathematical induction, the necessary condition holds.
728x90
반응형