Sum of weight of edges of each vertex of a $4$ regular graph can be made $0$.

Question

Suppose we have $4$ regular graph $G$. We have to show that each edge can be labelled with $-1$ or $1$ such that the total flow in a vertex is $0$.

There is also a question related to it:

To find an example of a $6$ regular graph where this type of edge labelling is not possible.

---

I am finding it difficult to prove the fact. I tried the method of contradiction.

I also thought of rephrasing the problem: In any $4$ regular graph, the edges can be given direction such that the in-degree and out-degree are the same for each vertex.

Can someone provide some hints on how to proceed?

Answer 1

Wlog we can assume the graph is connected.

Notice that the number of edges is, by handshake lemma, even.

This graph is Eulerian since each node has even degree. So we have Euler cycle $E$ in it. Let start at node $v$ and label ecah edge on $E$ alternatively with $1$ and $-1$ on this cycle starting with $+1$ at $v$.

Clearly this procedure gives the desired labelling.

---

Clearly $K_7$, which is $6$-regular graph, does not have such a labelling: If it would have then make a new graph where two nodes are connected iff edge between them has labelling $1$. Then we get a $3$-regular graph on $7$ vertices which existence is contradicting handshake lemma.

Answer 2

Aqua's answer is correct. However, as pointed out by MJD, it should be noted that since the graph is 4-regular, from Handshaking Lemma the number of edges must be even.