Iranian Mathematical Olympiad

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 $4$ 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 $3$, 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 $5$ vertices. $10$ equations with integer coefficients, for $10$ 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 $w_e$ be the weight of edge $e$ and $W_T$ be the weight of triangle $T$. It suffices to prove the claim when $$w_e=\{\begin{array}{ll}1& e=e_0\\ 0& e\ne e_0\end{array}$$ Let $|T\cap e|$ be the number of mutual vertices between triangle $T$ and edge $e$. Therefore, it is concluded that $$W_T=\{\begin{array}{ll}\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{array}$$ So, the equation system has a solution in real numbers. Now consider the numbers $w_e$ with the desired property. The value of each $W_T$ is calculated as a linear combination of $w_e$'s as $$W_T=\frac{1}{3}\sum _{e:|T\cap e|\ne 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 $\frac{1}{3}{\sum }_e{w}_e$ is an integer number and also ${\sum }_{e:|T\cap e|=1}{w}_e$ is an even number. Hence the claim for $5$ vertices is proved.

Assume the claim for a complete graph with $k$ vertices. Now consider a complete graph with $k+1$ vertices. Label the vertices of this graph by $v,u_1,u_2,\dots ,u_n$, and let $w_i$ be the number assigned to edge $v{u}_i$, and let $x_{\{i,j\}}$ be the number that is going to be assigned to the triangle $v{u}_i{u}_j$. In this case $$\sum _{t\ne j}{x}_{\{t,j\}}=w_t.$$ Now given that $w_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 $k\ge 3$. However, the claim is true for $k\ge 3$; For $k=3$, the desired values are $$x_{\{1,2\}}=\frac{w_1+w_2-w_3}{2},x_{\{2,3\}}=\frac{w_2+w_3-w_1}{2},x_{\{3,1\}}=\frac{w_3+w_1-w_2}{2},$$ and since $w_1+w_2+w_3$ is an even number, the $x_{\{i,j\}}$'s are integers. Now assuming that for $k$, $x_{\{i,j\}}$, $i,j\le k$'s are integers, for $k+1$ it is deduced that $$x_{\{k,k+1\}}=w_{k+1},\forall 1\le i\le k:x_{\{i,k+1\}}=0,$$ $$\text{Let }{c}_j:=\sum _{\begin{array}{c}j=1\\ j\ne i\end{array}}^k{x}_{\{i,j\}},\forall 1\le i\le k⟹1\le i<k:w_i=c_i,c_k=w_k-w_{k+1}⟹\sum _{i=1}^k{c}_i=\sum _{i=1}^k{w}_i-2w_{k+1},$$ meaning ${\sum }_{i=1}^k{c}_i$ is an even number, and therefore, according to the assumption, equations $$\sum _{\begin{array}{c}j=1\\ j\ne t\end{array}}^k{x}_{\{t,j\}}=c_t$$ lead to integer solutions, and so $$\sum _{\begin{array}{c}j=1\\ j\ne t\end{array}}^{k+1}{x}_{\{t,j\}}=w_t$$ also lead to integer solutions.

Now assume that $y_{\{i,j\}}$ is the number assigned to edge $u_i{u}_j$. Consider a complete graph with vertices $u_1,u_2,\dots ,u_k$ and assign the weight $y_{\{i,j\}}-x_{\{i,j\}}$ to edge $u_i{u}_j$. Thus the sum of the weights of the edges containing a vertex $u_t$ equals to $$\sum _{\begin{array}{c}j=1\\ j\ne t\end{array}}^k(y_{\{t,j\}}-x_{\{t,j\}})=\sum _{\begin{array}{c}j=1\\ j\ne t\end{array}}^k{y}_{\{t,j\}}-w_t\stackrel{2}{=}\sum _{\begin{array}{c}j=1\\ j\ne t\end{array}}^k{y}_{\{t,j\}}+w_t,$$ which is the same number obtained when calculating the sum of the weight of edges containing $u_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 $$\begin{array}{rl}\sum _{i\ne j}(y_{\{i,j\}}-x_{\{i,j\}})& =\sum _{i\ne j}{y}_{\{i,j\}}-\sum _{i\ne j}{x}_{\{i,j\}}\\ & =\sum _{i\ne j}{y}_{\{i,j\}}-2\sum _{i=1}^k{w}_i\stackrel{3}{=}\sum _{i\ne j}{y}_{\{i,j\}}+2\sum _{i=1}^k{w}_i,\end{array}$$ 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 $4$ vertices in the graph defined in the statement of the problem. Assign the weight $1$ to all the edges in the subgraph, and $0$ 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 $3$, the total sum of the weights of the subgraph is also a multiple of $3$. 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 $3$ vertices, the subgraph is either the triangle itself or does not contain any edge; Respectively, it suffices to assign weight $1$ and $0$ to the only triangle of the graph.

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

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