Prove that the for all , we can arrange the number on edges of a complete graph with vertices so that the sum of the numbers assigned to edges of any length three path (possibly closed) is not less than .
Solution
To prove that for all , we can arrange the numbers on the edges of a complete graph with vertices so that the sum of the numbers assigned to the edges of any length three path (possibly closed) is not less than , we can proceed as follows:
1. Split the vertices into two sets:
Let and be two sets such that . Specifically, let and . This ensures that the sizes of and are as balanced as possible.
2. Assign numbers to edges between sets:
For any edge where and , assign an integer less than or equal to . This means that the edges between the two sets and will have the smallest numbers assigned to them.
3. Assign remaining numbers to other edges:
Assign any of the remaining values to all the other edges, i.e., the edges within set and within set .
4. Analyze the sum of numbers in any triangle:
Consider any triangle in the graph. At least one of the edges of the triangle must join two vertices that are either both in or both in . The number assigned to this edge is at least .
5. Compare with the required bound:
Since is a lower bound for the sum of the numbers assigned to the edges of any triangle, we need to show that this is greater than or equal to .
6. Verify the inequality:
For large , grows much faster than and . Therefore, for , the inequality holds true.