Maths Olympiad Prep

Library / /88 of 92

Combinatorics Difficulty 7.6 National olympiad, round 2 Prove it Iran

A subgraph of a KnK_n is chosen such that the number of its edges is a multiple of 33 and the degree of each vertex is an even number. Prove that we can assign an integer weight to each triangle of the KnK_n such that for each edge of the chosen subgraph, the sum of the weight of the triangles that contain that edge equals 11, and for each edge that is not in the subgraph, this sum is 00.

Solution

The following lemma is needed to approach the solution:
Lemma. If some integer weight is assigned to any edge of a complete graph with more than 44 vertices, such that for each vertex, the sum of the weight of the edges connected to this vertex is an even number, and the sum of the weight of all edges is a multiple of 33, then it is possible to assign some weights to each triangle of the graph such that the sum of the weight of all triangles containing an edge equals the weight of that edge.

Proof. This lemma is proved using induction.
The base of induction is when the graph has 55 vertices. 1010 equations with integer coefficients, for 1010 variables can be obtained when considering each edge and triangles containing it. Firstly, these equations have a solution in real numbers. To show this, it suffices to show that the characteristic function for the weight of each edge is linear in its range. Let wew_e be the weight of edge ee and WTW_T be the weight of triangle TT. It suffices to prove the claim when
we={1e=e00ee0 w_e = \begin{cases} 1 & e = e_0 \\ 0 & e \neq e_0 \end{cases}
Let Te|T \cap e| be the number of mutual vertices between triangle TT and edge ee. Therefore, it is concluded that
WT={13Te0=216Te0=113Te0=0 W_T = \begin{cases} \frac{1}{3} & |T \cap e_0| = 2 \\ -\frac{1}{6} & |T \cap e_0| = 1 \\ \frac{1}{3} & |T \cap e_0| = 0 \end{cases}
So, the equation system has a solution in real numbers. Now consider the numbers wew_e with the desired property. The value of each WTW_T is calculated as a linear combination of wew_e's as
WT=13e:Te1we16e:Te=1we=13ewe12e:Te=1we, W_T = \frac{1}{3} \sum_{e: |T \cap e| \neq 1} w_e - \frac{1}{6} \sum_{e: |T \cap e| = 1} w_e = \frac{1}{3} \sum_e w_e - \frac{1}{2} \sum_{e: |T \cap e| = 1} w_e,
which is an integer number; That is because 13ewe\frac{1}{3} \sum_e w_e is an integer number and also e:Te=1we\sum_{e: |T \cap e| = 1} w_e is an even number. Hence the claim for 55 vertices is proved.

Assume the claim for a complete graph with kk vertices. Now consider a complete graph with k+1k+1 vertices. Label the vertices of this graph by v,u1,u2,,unv, u_1, u_2, \dots, u_n, and let wiw_i be the number assigned to edge vuivu_i, and let x{i,j}x_{\{i,j\}} be the number that is going to be assigned to the triangle vuiujvu_iu_j. In this case
tjx{t,j}=wt. \sum_{t \neq j} x_{\{t,j\}} = w_t.
Now given that wiw_i's are integers with even sum, we prove that the latest equation leads to an integer solution. This is also proved using induction; It's needed to prove this claim for k3k \ge 3. However, the claim is true for k3k \ge 3; For k=3k=3, the desired values are
x{1,2}=w1+w2w32,x{2,3}=w2+w3w12,x{3,1}=w3+w1w22, x_{\{1,2\}} = \frac{w_1 + w_2 - w_3}{2}, \quad x_{\{2,3\}} = \frac{w_2 + w_3 - w_1}{2}, \quad x_{\{3,1\}} = \frac{w_3 + w_1 - w_2}{2},
and since w1+w2+w3w_1 + w_2 + w_3 is an even number, the x{i,j}x_{\{i,j\}}'s are integers. Now assuming that for kk, x{i,j}x_{\{i,j\}}, i,jki, j \le k's are integers, for k+1k+1 it is deduced that
x{k,k+1}=wk+1,1ik:x{i,k+1}=0, x_{\{k,k+1\}} = w_{k+1}, \quad \forall 1 \le i \le k : x_{\{i,k+1\}} = 0,
Let cj:=j=1jikx{i,j},1ik    1i<k:wi=ci,ck=wkwk+1    i=1kci=i=1kwi2wk+1, \text{Let } c_j := \sum_{\substack{j=1 \\ j \neq i}}^{k} x_{\{i,j\}}, \quad \forall 1 \le i \le k \implies 1 \le i < k : w_i = c_i, \quad c_k = w_k - w_{k+1} \implies \sum_{i=1}^{k} c_i = \sum_{i=1}^{k} w_i - 2w_{k+1},
meaning i=1kci\sum_{i=1}^{k} c_i is an even number, and therefore, according to the assumption, equations
j=1jtkx{t,j}=ct \sum_{\substack{j=1 \\ j \neq t}}^{k} x_{\{t,j\}} = c_t
lead to integer solutions, and so
j=1jtk+1x{t,j}=wt \sum_{\substack{j=1 \\ j \neq t}}^{k+1} x_{\{t,j\}} = w_t
also lead to integer solutions.

Now assume that y{i,j}y_{\{i,j\}} is the number assigned to edge uiuju_i u_j. Consider a complete graph with vertices u1,u2,,uku_1, u_2, \dots, u_k and assign the weight y{i,j}x{i,j}y_{\{i,j\}} - x_{\{i,j\}} to edge uiuju_i u_j. Thus the sum of the weights of the edges containing a vertex utu_t equals to
j=1jtk(y{t,j}x{t,j})=j=1jtky{t,j}wt=2j=1jtky{t,j}+wt, \sum_{\substack{j=1 \\ j \neq t}}^{k} (y_{\{t,j\}} - x_{\{t,j\}}) = \sum_{\substack{j=1 \\ j \neq t}}^{k} y_{\{t,j\}} - w_t \stackrel{2}{=} \sum_{\substack{j=1 \\ j \neq t}}^{k} y_{\{t,j\}} + w_t,
which is the same number obtained when calculating the sum of the weight of edges containing utu_t in the first graph; Therefore the calculated number is an even number. Also, the sum of assigned weights to all the edges equals to
ij(y{i,j}x{i,j})=ijy{i,j}ijx{i,j}=ijy{i,j}2i=1kwi=3ijy{i,j}+2i=1kwi, \begin{aligned} \sum_{i \neq j} (y_{\{i,j\}} - x_{\{i,j\}}) &= \sum_{i \neq j} y_{\{i,j\}} - \sum_{i \neq j} x_{\{i,j\}} \\ &= \sum_{i \neq j} y_{\{i,j\}} - 2 \sum_{i=1}^{k} w_i \stackrel{3}{=} \sum_{i \neq j} y_{\{i,j\}} + 2 \sum_{i=1}^{k} w_i, \end{aligned}
which again, is the same number when calculating the sum of all the assigned weights in the previous graph; Thus, the calculated number is a multiple of three.

Therefore, according to the induction assumption, it is possible to assign some weights to the triangles of the graph such that the sum of the weights of the triangles containing an edge equals to the weight assigned to the edge itself.

Now assigning the same obtained weights to the first graph, the desired property is held and therefore the lemma is proved. □

Back to the problem.
Assume that there are more than 44 vertices in the graph defined in the statement of the problem. Assign the weight 11 to all the edges in the subgraph, and 00 to the others. Therefore, since the degree of each vertex in the subgraph is an even number, the sum of the weights of the edges containing it is an even number. Again, since the number of edges in the subgraph is a multiple of 33, the total sum of the weights of the subgraph is also a multiple of 33. Hence, according to the lemma, it is possible to assign some weights to the triangles of the graph so that the desired property is satisfied.

In case when the graph has 33 vertices, the subgraph is either the triangle itself or does not contain any edge; Respectively, it suffices to assign weight 11 and 00 to the only triangle of the graph.

If the number of vertices of the graph is exactly 44, the graph has 66 edges. Thus, the subgraph either has 66 edges, 33 edges or 00 edges. If the number of edges of the subgraph is 66, it is concluded that the subgraph is the graph itself and therefore the degree of each vertex is 33, a contradiction. If the number of edges is 33, then the subgraph is a triangle along with an isolated vertex; So it suffices to assign weight 11 to the triangle that all its edges are selected, and 00 to the others.

In case when the graph has no edges, it suffices to assign weight 00 to all triangles. ■

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.