# Direct edges of undirected graph so that all indegrees are even

Undirected graph is given which has M edges and N vertices we have to convert every edge from $$u-v$$ to $$u\to v$$ or $$v\to u$$ such that the total indegree of every vertex is even.

For example, consider a graph which has the edges 1-2, 1-3, 2-4, 3-4. We can direct it as 1→2, 1→3, 2←4, 3←4, so indegrees of 1,2,3,4 are respectively 0,2,2,0, which are all even.

Which method or algorithm is suited for least time complexity? M and N are between 1 and 100,000.

• There is no such algorithm as this is not always possible. In a $K_2$, regardless of how you orient $uv$, the in-degree of $u$ or $v$ is 1, which is not even. – Juho Dec 9 '18 at 13:14
• Please credit the original source of the problem in the question. – John L. Dec 10 '18 at 1:37
• @Juho More generally, it's impossible if the number of edges is odd. – David Richerby Dec 11 '18 at 10:54
• Please block this question, this is a question from a competition codechef.com/DEC18B/problems/EDGEDIR – Sahil Kumar Dec 12 '18 at 13:40
• It might be too late now, unfortunately. It’s only fair to let anyone use the solution. – Yuval Filmus Dec 12 '18 at 17:24

Orient all edges in an arbitrary fashion, and add a $$0/1$$ variable $$x_{u,v}$$ for each edge $$(u,v)$$, with the following meaning: $$x_{u,v} = 0$$ means that we use the orientation $$u \to v$$, and $$x_{u,v} = 1$$ means that we use the orientation $$u \gets v$$. The parity of the indegree of $$u$$ is equal to $$\sum_{(u,v) \in E} x_{u,v} + \sum_{(w,u) \in E} (1 + x_{w,u}) \pmod{2}.$$ Let $$p_u$$ be the parity of the number of edges of the form $$(w,u)$$. Then we can formulate the task as follows:

Assign $$0/1$$ values to the edges so that the sum of weights of edges adjacent to $$u$$ is $$p_u$$ (mod 2).

As an example, consider your sample graph, with edges $$(1,2), (1,3), (2,4), (3,4).$$ We have $$p_1 = 0$$, $$p_2 = 1$$, $$p_3 = 1$$, $$p_4 = 0$$. We are looking for a solution (mod 2) of the following system: \begin{align*} &x_{12} + x_{13} = 0 \\ &x_{12} + x_{24} = 1 \\ &x_{13} + x_{34} = 1 \\ &x_{24} + x_{34} = 0 \end{align*}

One such solution is $$x_{12} = x_{13} = 0$$, $$x_{24} = x_{34} = 1$$. This is exactly the solution that you describe.

If you sum all equations, then all the edges cancel, and you get $$\sum_u p_u = 0 \pmod{2}$$. This gives a necessary condition for the existence of a solution. It turns out that this condition is also sufficient, assuming the graph is connected (otherwise, you need a similar condition for each connected component). A solution can be found using linear algebra modulo 2.

This is related to the so-called Tseitin contradictions in proof complexity, which correspond to assignments of the weights $$p_u$$ for which no solution exists.

• Please block this question, this is a question from a competition codechef.com/DEC18B/problems/EDGEDIR – Sahil Kumar Dec 12 '18 at 13:43