# Decide if the edges of a mixed graph can be directed in order to be an Eulerian Graph

I'm very stuck with this problem. Given $$G = (V, E, A)$$ a mixed graph where every edge in $$E$$ is directed and every edge in $$A$$ is undirected. Thinking as a max-flow problem, decide if it's possible to give a direction to every $$a \in A$$ in order to make $$G$$ an $$eulerian$$ graph.

The model I've thinking so far is to translate the problem as a matching problem. For every non directed edge, I would like to determine to which node this will point. For example, if $$e=(u,v)$$, from the vertex source there should be an edge connecting to $$e$$ and this one will be connected to $$u$$ and $$v$$. Every edge will have a flow capacity of 1, except for the edges of the target, which will have a capacity of $$?$$. I don't know if this model it's okay, but any clue (or another model) will help, thanks!

You want each node to have the same number of incoming and outgoing edges.

Let $$\alpha(v)$$ be the number of edges in $$A$$ outgoing in $$v$$ minus the number of edges in $$A$$ outgoing from $$v$$. Consider the graph $$H=(V,E)$$ and let $$\delta(v)$$ be the degree of $$v$$ in $$H$$.

We need to find an orientation of the edges in $$H$$ such that each vertex $$v$$ has an out-degree that is exactly its in-degree minus $$\alpha(v)$$. In other words, if $$k$$ is the number of edges in $$E$$ that need to be oriented towards $$v$$, we must have: $$\delta(v) - k(v) = k(v) - \alpha(v),$$ equivalently: $$k(v) = \frac{\delta(v) + \alpha(v)}{2},$$ where we can assume that all $$k(v)$$s are non-negative integers and that $$|E| = \sum_{v \in V} k(v)$$ (otherwise there is no feasible orientation).

Create a graph $$H' = (\{s,t\} \cup E \cup V, F)$$ where $$F$$ contains the following directed edges:

• All edges in $$\{s\} \times E$$ with capacity $$1$$;
• An edge $$(v,t)$$ with capacity $$k(v)$$ for each in $$v \in V$$.
• Two edges $$(e, u)$$ and $$(e, v)$$, both of capacity $$1$$, for each $$e \in E$$.

Now compute a max flow $$f$$ from $$s$$ to $$t$$ in $$H'$$ and check whether its value $$|f|$$ is exactly $$\sum_{v \in V} k(v)$$.

If that's the case at least one valid orientation exists and it can be found by orienting $$e = (u,v) \in E$$ towards the unique endpoint $$x \in \{u,v\}$$ such that $$f( \, (e,x) \, ) = 1$$.

• Didn't expect something so formal, thanks :) – Lisandro Di Meo Jun 16 at 16:49