On each edge of a graph is written a real number,such that for every even tour of this graph,sum the edges with signs alternatively positive and negative is zero.prove that one can assign to each of the vertices of the graph a real number such that sum of the numbers on two adjacent vertices is the number on the edge between them.(tour is a closed path from the edges of the graph that may have repeated edges or vertices)
Problem
Source: Iran TST 2013:TST 2,Day 2,problem 1
Tags: combinatorics proposed, combinatorics
25.04.2013 12:02
Let denote the graph by $G$ , the number assigned to the edge $e\in E(G)$ - by $n(e)$ and the number that will be assigned to a vertex $v\in V(G)$ - by $n(v)$. Assume that $G$ is a connected graph (if not, we will apply the arguments below to each connected component of $G$). Let $T$ ia a spanning tree of $G$ with a root $v_0$. Assign to $v_0$ , for now being, an arbitrary number $n_0$ , i.e $n(v_0)=n_0$. We will choose $n_0$ later. We can consecutively assign numbers to the vertices of $T$, so that for every edge $xy$ of $T$ holds: $n(xy)=n(x)+n(y)$. Our aim is to prove that the same holds for every edge $e\in E(G)\setminus E(T)$. Let $xy$ is an edge of $E(G)\setminus E(T)$ connecting $x,y\in T$. Consider the closed path $p = x T v_0 T y x$, where $xTy$ means the unique path in $T$ connecting the vertices $x$ and $y$. Of course $p$ may have repeated edges. If the length of $p$ is even then applying the given property an easy calculation yields $n(uv)=n(u)+n(v)$. But the length of $p$ may be odd. So if all these paths are with even length we are done. Now assume $x_0y_0 \in E(G)\setminus E(T)$ so that the path $p = x_0 T v_0 T y_0 x_0$ has an odd length. It's time now to determine $n_0=n(v_0)$ so that to hold: $n(x_0y_0)=n(x_0)+n(y_0)$. An easy calculation shows that it is possible. Now if $xy$ is an arbitrary edge of $G\setminus T$ and the length of path: $p=x T v_0 T y x$ is odd we consider a new closed path: $p'=v_0 T x y T v_0 T x_0 y_0 T v_0$. The length of $p'$ is even as a sum of two paths with odd lengths. For each edge of $p'$ except $xy$ , the number assigned to that edge is sum of numbers assigned to its incident vertices. Now using the given condition an easy calculation shows that it is also true for $xy$. Comment: I think an easy one for a TST. There is a clear motivation and more efforts are needed to write it than to solve it.
15.11.2019 09:06
Can someone explain how it is easy to conclude $n(uv)=n(u)+n(v)$ if $p$ is even. I think $u$ and $v$ should be $x$ and $y$ as well.