Edge labeling on oriented graph (Tutte related)
Source: Tuymaada 2012, Problem 8, Day 2, Seniors
July 21, 2012
abstract algebragraph theorycombinatorics proposedcombinatorics
Problem Statement
Integers not divisible by are arranged on the arcs of an oriented graph. We call the weight of a vertex the difference between the sum of the numbers on the arcs coming into it and the sum of the numbers on the arcs going away from it. It is known that the weight of each vertex is divisible by . Prove that non-zero integers with absolute values not exceeding can be arranged on the arcs of this graph, so that the weight of each vertex is zero.Proposed by W. Tutte