A sub-graph of a complete graph with $n$ vertices is chosen such that the number of its edges is a multiple of $3$ and degree of each vertex is an even number. Prove that we can assign a weight to each triangle of the graph such that for each edge of the chosen sub-graph, the sum of the weight of the triangles that contain that edge equals one, and for each edge that is not in the sub-graph, this sum equals zero. Proposed by Morteza Saghafian
Problem
Source: Iranian TST 2019, third exam day 2, problem 5
Tags: combinatorics
25.06.2019 16:05
Sketch: We first prove the claim when the subgraph is a triangle. In that case we assign weight $1$ to this triangle and $0$ to all the remaining triangles of the complete graph. Clearly that assignment satisfies the condition. Further, it can be proved that each (sub)graph with number of edges multiple of $3$ and all degrees even, can be constructed by adding and subtracting simple triangles. It involves some cases and may be proved via partitioning the (sub)graph into cycles. Finally, we sum up triangle-wise (with signs) the corresponding assignments to each simple triangle and the result follows.
05.07.2019 03:02
Here is a troll solution, which shows that the conditions "number of its edges is a multiple of $3$" and "degree of each vertex is even" are not necessary when $n \ge 5.$ Start by labelling every edge with the number $0$ initially. We will define an operation as selecting three distinct vertices $a, b, c$ and increasing the label of edges $ab, bc, ca$ by some real number $x \in \mathbb{R}.$ It suffices to show that we can make all labels of the edges in the sub-graph equal to $1$ and labels of all other edges equal to $0$ with a finite number of operations. For $n \le 4$, the only such sub-graphs are triangles, and so the problem is trivial with one operation. Otherwise, suppose that $n \ge 5.$ Lemma. For any two edges $e_1, e_2$ and any $x \in \mathbb{R}^{+}$, there exists a finite number of operations which increase the label of $e_1$ by $x$, decrease the label of $e_2$ by $x$, and leave all other labels unchanged. Proof. We consider two cases. Case 1. $e_1, e_2$ do not share a vertex. Let $e_1 = ab, e_2 = cd$, where $a, b, c, d$ are distinct vertices. Then, apply the following four operations in order. 1) Increase the labels of edges $ab, bc, ca$ by $\frac{x}{2}$. 2) Increase the labels of edges $ab, bd, da$ by $\frac{x}{2}$. 3) Decrease the labels of edges $cd, db, bc$ by $\frac{x}{2}$. 4) Decrease the labels of edges $cd, da, ac$ by $\frac{x}{2}$. It's easy to see that these four operations, when done successively, yield the desired outcome. Case 2. $e_1, e_2$ share a vertex. Let $e_1 = ab, e_2 = ac,$ where $a, b, c$ are distinct vertices. Then, select some other vertices $d, e$, which exist because $n \ge 5$. Finally, simply use Case 1 of the lemma as follows. 1) Increase the label of $ab$ by $x$, and decrease the label of $de$ by $x$. 2) Increase the label of $de$ by $x$, and decrease the label of $ac$ by $x$. It's easy to see that the result of the successive application of the two above processes yields the desired result. $\blacksquare$ As a result of the lemma, if we view the labels of the edges as "wealth," we can now essentially distribute wealth arbitrarily amongst the edges, as long as the total wealth of all edges remains constant. Hence, if the desired total wealth is $x$, then we can simply increase $ab, bc, ca$ by $\frac{x}{3}$ for some arbitrary three vertices $a, b, c$, and then use the lemma to distribute this wealth into the desired configuration. We are now done. $\square$
04.03.2020 10:14
Linear Algebra We prove the statement for general graphs with at least $7$ vertices. We have the $\binom{n}{3}$ equations $A\mathbf{w}=\mathbf{b}$, where $A$ is a $\binom{n}{2} \times \binom{n}{3}$ matrix such that $A_{e, T}=1$ iff $e$ is an edge of $T$, $\mathbf{w}$ is the vector of unknown weights of all $\binom{n}{3}$ triangles, and $\mathbf{b}$ is an indicator vector of edges(i.e. the entry is $1$ iff the edge is in the graph). It suffices to prove that $A$ has full row rank. FTSOC suppose that $A$ is not of full row rank. Then we have a linear combination of row vector giving the zero vector. Now write these coefficients on the edges of the graph. Color the edges with positive numbers red, and black for negative values, and delete the edge otherwise. Then we have the property that for every triangle of the graph, the number of the three edges sum up to zero. We claim that this is only possible if all edges are uncolored. Let $G_1$ be the graph with red edges, and $G_2$ be the graph with black edges. Note that if two edges of a triangle are of same color, then the other edge must be present and has different color with the other two. Hence, if $\{ v, x\},\{ v, y\},\{ v, z\}$ are of same color, then $xyz$ is monochromatic, which is impossible. Thus we have $d_{G_1}(v) \le 2$ and $d_{G_2}(v) \le 2$ for every vertex $v$. Now fix a red edge $\{x,y\}$, then for every $v \neq x,y$, either $\{v,x\}$ or $\{v,y\}$ is black. Hence by pigeonhole we have $$3 >\max\{d_{G_2}(x), d_{G_2}(y) \} \ge \left\lceil\frac{n-2}{2}\right\rceil \ge \left\lceil\frac{5}{2}\right\rceil =3,$$a contradiction. Thus the only case is that there are no red edges at all. This holds similarly for the black edges, so all edges are uncolored. We're done.
15.04.2020 08:58
More direct way using Linear Algebra.
between triangle and edges has a full rank. This is equivalent to "There exists linearly independent $n \choose 2$ columns". From now, name each vertex by $1,2,...,n$ and denote $(a,b,c)$ to represent the column and $(a,b)$ to represent the row of corresponding triangle and edges. We will directly give the linearly independent columns: all triangles in forms of $(1,i,j), (2,3,k)$ and $(2,4,5),(3,4,5)$. For the sake of contradiction, assume they are linearly dependent. By definition, there exists $a_{i,j}, b_{k}, c,d$ not all zero satisfying $$\sum a_{i,j} (1,i,j)+\sum b_k (2,3,k) + c(2,4,5)+d(3,4,5)=0$$ (1) Since $(i,j)$ only appears on $(1,i,j)$, $a_{i,j}=0$ for $3<i<j$ except for $(1,4,5)$. (2) Considering $(1,k), (2,k)$ and $(3,k)$ for $k>5$, we get $a_{2,k}+a_{3,k}=0$, $a_{2,k}+b_k=0$ and $a_{3,k}+b_k=0$. Therefore, $a_{2,k}=a_{3,k}=b_k=0$ for $k>5$. After (1),(2), the remaining columns are $(a,b,c)$ with $1 \le a < b< c\le 5$. They should be linearly dependent by assumption. However, the determinant of restricted $10 \times 10$ matrix with edges and triangles between $1,2,3,4,5$ is not zero and therefore they are in fact linearly independent. Therefore, the incidence matrix has the full rank and the problem holds for general cases: any number given for the edges.
15.04.2020 10:52
For $n \ge 5$, we can prove that we can assign a weight to each triangle which satisfies the conditions. step 1) If there are only $1$ white edge, there exists a way to assign a weight. Let’s say there are $n$ vertexes named with $A_{1}, A_{2}, ..., A_{n}$ and only $A_{1}A_{2}$ is white. Then, we can assign a weight to each triangle like following. Triangle $A_{1}A_{2}A_{3}$, $A_{1}A_{2}A_{4}$, $A_{1}A_{2}A_{5}$, and $A_{3}A_{4}A_{5}$ are $\frac{1}{3}$, and triangle $A_{1}A_{3}A_{4}$, $A_{1}A_{3}A_{5}$, $A_{1}A_{4}A_{5}$, $A_{2}A_{3}A_{4}$, $A_{2}A_{3}A_{5}$, and $A_{2}A_{4}A_{5}$ are $-\frac{1}{6}$, and the others are all $0$. step 2) For all graphs $G$, there exists a way to assign a weight. Let’s say there are $m$ white edges named with $e_{1}, e_{2}, ..., e_{m}$ . And, $G_{i}$ is a graph which has the same vertexes as $G$ and only $e_{i}$ is white. By step 1, we can assign a weight to each triangle on the graph $G_{i}$. If the weight of $G_{1}$’s triangle $A_{i}A_{j}A_{k}$, $G_{2}$’s triangle $A_{i}A_{j}A_{k}$, ..., and $G_{m}$’s triangle $A_{i}A_{j}A_{k}$ are assigned to $G$’s triangle $A_{i}A_{j}A_{k}$, the conditions of the problem are satisfied. $\blacksquare$
07.08.2020 10:55
The right statement should be Official booklet wrote: A subgraph of a$ K_n$ is chosen such that the number of its edges is a multiple of $3$ and degree of each vertex is an even number. Prove that we can assign an integer weight to each triangle of the $K_n$ such that for each edge of the chosen subgraph, the sum of the weight of the triangles that contain that edge equals one, and for each edge that is not in the subgraph, this sum is zero. So maybe OP missed the condition of integer weight. In this manner, the condition mentioned in #3 is no longer redundant.