A weighted complete graph with distinct positive wights is given such that in every triangle is degenerate that is wight of an edge is equal to sum of two other. Prove that one can assign values to the vertexes of this graph such that the wight of each edge is the difference between two assigned values of the endpoints. Proposed by Morteza Saghafian
Problem
Source: Iran TST1 Day1 P1
Tags: combinatorics, graph theory, Iranian TST
23.02.2020 03:11
Let $f(uv)$ denote the edge weight of an edge $uv$. In every triangle, there is one large edge and two small edges. Say a vertex $v$ is weak if, for all triangles containing $v$, the large edge of that triangle is incident to $v$. Let $AB$ be the edge with maximum weight $f(AB)=M$. We claim that $A$ is weak: indeed, suppose for the sake of contradiction that there exists some triangle $ACD$ where $f(AC) + f(AD) = f(CD)$. By maximality of $M$, the edge weights of triangle $BCD$ are $\{M-f(AC), M-f(AD), f(AC)+f(AD)\}$, but it is easy to check that we cannot add two of these to make the third: either we get an edge with weight $0$ or we get $f(CD)=M$, contradicting distinctness. Now we construct out vertex-labeling: set $w(A)=0$ and for each other vertex $X$ set $w(X) = f(AX)$. By construction, this vertex labeling works on all edges incident to $A$, so consider an arbitrary edge $XY$ not containing $A$. Since $A$ is weak, if we WLOG assume that $w(X)<w(Y)$, then $AY$ is the large edge of triangle $AXY$ and we obtain $f(XY) = f(AY) - f(AX) = w(Y)-w(X)$. This means that our vertex labeling works on $XY$, so it works on all edges and we are done.
25.02.2020 19:48
nice solution i have 2 solutions for this one is induction if we use an special induction we really just don't need to do anything but to check n=3 and n=4 for my second solution pay attention that if we say that weights are distance then the graph would be a line with some points on it take this as a hint it will solve the problem easily
20.08.2020 14:08
Mr.C wrote: nice solution i have 2 solutions for this one is induction if we use an special induction we really just don't need to do anything but to check n=3 and n=4 for my second solution pay attention that if we say that weights are distance then the graph would be a line with some points on it take this as a hint it will solve the problem easily Do you mean to say like assigning a vector coordinate at each vertex?
20.08.2020 16:14
yayitsme wrote: Mr.C wrote: nice solution i have 2 solutions for this one is induction if we use an special induction we really just don't need to do anything but to check n=3 and n=4 for my second solution pay attention that if we say that weights are distance then the graph would be a line with some points on it take this as a hint it will solve the problem easily Do you mean to say like assigning a vector coordinate at each vertex? yeah sure , if $E(u,v)$ is the weight of the edge between $u,v$ there exists a represintation of the ghraph in the "plane" such that $D(u,v)=E(u,v)$ you need to prove this in the first part, next you can easily check that the geaph will form a line , and the rest is easy ...
28.07.2024 20:42
Mr.C wrote: one is induction if we use an special induction we really just don't need to do anything but to check n=3 and n=4 how induction works? (check n=3 and n = 4 is easy how is the rest?)