GoldenFrog1618 wrote:

What if the edge $\{v_j,v_k\}$ has already existed? Ah is it okay that $G$ has multiedges?

A very nice problem.First,let's consider edges with weights $1$ and with weights $2$ seperately.Now,note that if we have a cycle with vertices $v1,v2,...vn$ such that all edges ${v1,v2},{v2,v3},...{vn,v1}$ have the same weight,we can remove edges of that cycle and nothing will change,so we may assume that our graph has no one-weighted cycles.Now,we will give orientation to each by this algorithm:We will build a new graph in the following way(vertices of that graph are the same as in this one): Consider the longest "walk" of $1$-s.Consider the two "ends" of that walk.Now,in our "new" graph those two vertices will be connected and also note that the degree of $1$-s of those two end vertices is $1$(our graph doesn't contain a cycle).Now,every "walk" we will oriendted the edges in this way:$v1->v2->v3..-vn$ or in the reverse order $vn->vn-1->...v1$(we will decide later). later).Now,consider the graph without those edges and repeat this algorithm.The important thing is that every vertex will be a "end" edge of a "walk" exactly once and that if we want that the difference of the in and out edges of $1$-s is $1$,it is not important which orientation are the walks.Now,do the same thing with $2$-s and all the same things will hold expect that every vertex will be an "end" edge in some "walk"(but that is even not important,we can assume that every will be and also connect "end" edges in our new graph).Now,from this pretty obvios fact we will end our problem :Let $G$ be a graph such that all vertices have degree at most two.It is possible to assign to each vertex a $1$ or $-1$ such that we can't have two vertices labeled with the same number such that beetwen them there is an edge.I will prove this if it is needed,but it is very easy.Now,if we apply this on our "new" graph,where if a vertex is labelled with $1$ then the difference of $1$-s is $1$ and if it is $-1$ it is $-1$,so now if two vertices $vi$ and $vj$ are respectively $1$ and $-1$ and are "end" edges of a walk of $2$-s,then we will orient it in this way:$vj->va->vb->...vi$ so we are finished. Though the solution is pretty long and mostly badly phrased,the main idea is simple,to consider independently $1$-s and $2$-s and then the thing with cycles and walks comes pretty natural.

At first, we repeat the operation 1 as many as possible. (operation 1):pick up a cycle from $G$ and orient the edges of the cycle to the same direction(clockwise or counterclockwise). Then the difference between the indegree and outdegree(we call it simply "difference") of each vertex is not changed, and non-oriented edges form some independence trees. Next, we repeat the operation 2 as many as possible. (operation 2):pick up a path of non-oriented edge from $G$ whose endpoint's degree of non-oriented is exactly one and orient the edges of the path to the same direction. Then, each vertex is selected as the endpoint of path exactly once, so each vertex's difference become 1. So, at the end of these operation, we will get a graph which follows the condition.

junioragd wrote: A very nice problem.First,let's consider edges with weights $1$ and with weights $2$ seperately.Now,note that if we have a cycle with vertices $v1,v2,...vn$ such that all edges ${v1,v2},{v2,v3},...{vn,v1}$ have the same weight,we can remove edges of that cycle and nothing will change,so we may assume that our graph has no one-weighted cycles.Now,we will give orientation to each by this algorithm:We will build a new graph in the following way(vertices of that graph are the same as in this one): Consider the longest "walk" of $1$-s.Consider the two "ends" of that walk.Now,in our "new" graph those two vertices will be connected and also note that the degree of $1$-s of those two end vertices is $1$(our graph doesn't contain a cycle).Now,every "walk" we will oriendted the edges in this way:$v1->v2->v3..-vn$ or in the reverse order $vn->vn-1->...v1$(we will decide later). later).Now,consider the graph without those edges and repeat this algorithm.The important thing is that every vertex will be a "end" edge of a "walk" exactly once and that if we want that the difference of the in and out edges of $1$-s is $1$,it is not important which orientation are the walks.Now,do the same thing with $2$-s and all the same things will hold expect that every vertex will be an "end" edge in some "walk"(but that is even not important,we can assume that every will be and also connect "end" edges in our new graph).Now,from this pretty obvios fact we will end our problem :Let $G$ be a graph such that all vertices have degree at most two.It is possible to assign to each vertex a $1$ or $-1$ such that we can't have two vertices labeled with the same number such that beetwen them there is an edge.I will prove this if it is needed,but it is very easy.Now,if we apply this on our "new" graph,where if a vertex is labelled with $1$ then the difference of $1$-s is $1$ and if it is $-1$ it is $-1$,so now if two vertices $vi$ and $vj$ are respectively $1$ and $-1$ and are "end" edges of a walk of $2$-s,then we will orient it in this way:$vj->va->vb->...vi$ so we are finished. Though the solution is pretty long and mostly badly phrased,the main idea is simple,to consider independently $1$-s and $2$-s and then the thing with cycles and walks comes pretty natural. There is actually an easier way to construct the walks in the $1-weighted$ graph. Since all vertices are of an odd degree, there must be an even number of vertices: $\{ v_1,v_2,\ldots v_{2n}\}$. So if we add a vertex $t$ and connect it to all the other vertices, all vertices in the new graph will have an even degree. This means that there is an Euler cycle. So if we direct all edges in the way we pass through them in the Euler cycle, and then delete the vertex $t$ and the edges, connected to it, the remaining graph would have the property. However, I still don't understand the second part of the solution - combining the $2-weighted$ and $1-weighted$ graphs. I don't find it obvious . For instance, if the end of the walks are $(v_1;v_2), (v_3;v_4)....$ both $v_1$ and $v_2$ could be connected to $v_3$ with an edge of weight 2, which is problem I believe.

Kirilbangachev wrote: However, I still don't understand the second part of the solution - combining the $2-weighted$ and $1-weighted$ graphs. I don't find it obvious . For instance, if the end of the walks are $(v_1;v_2), (v_3;v_4)....$ both $v_1$ and $v_2$ could be connected to $v_3$ with an edge of weight 2, which is problem I believe. Yes, it’s either incorrect or not fully explained.

I think it is not,$v1$->$v2$,$v3$->$v4$,$v2$->$v3$->$v1$,everything is okay.I wanted to solve this again but I read the solution.So,every vertex will be an end of an exactly one $1$-walk.So,WLOG vertices are paired (v1,v2),(v3,v4),...(v2n-1,v2n).Also,we will have them somehow paired with 2s.Know we decide how to in which way to orient them.Every vertex has exactly one blue edge(paired with 1s end),and at most one red edge(with 2s).This graph will have components of the following kind: 1)Double edge v1 and v2 are paired with 1s and 2s,then we just orient them diferently. 2)A path BRBRBRBR...Just orient them from start of the path towards the end. 3)A cycle BRBRB... which we will alternate.Just orient it in the way of the cycle. 4)We cant have a component without blue edges(that would be a problem),it is clear that is impossible.

Take the graph theoretical interpretation, with a complete graph on $n$ vertices with edges weighted 1 and 2 such that the degree of each vertex is odd. We want to orient this so that the difference between indegree and outdegree is 1 for every vertex. First, note that $n$ must be even as the sum of degrees across all vertices must be twice the sum of the edge weights, which is even. Hence, each vertex is connected to an even number of 2-edges. Now, take subgraph of 2-edges. As each degree is even, this graph is Eulerian, so we may take an Eulerian cycle, orient the 2-edges along that cycle, and remove it from the graph. We are left with the classic problem of orienting a simple graph with each vertex degree odd such that the difference between indegree and outdegree is 1 for each vertex. Add a new vertex connected to every other vertex. As $n$ is even, this new graph has the property that all degrees are even, so it is Eulerian. Now, orient every edge of the original graph along an Eulerian path of the new graph, and note that it has the desired property.

The subgraph of 2s may not have all even degrees.

My mistake, I misread the graph as complete. In the general case, we may remove all 2-edge cycles and 1-edge cycles so we are left with a superposition of two forests on $n=2k$ vertices. Decompose each forest into paths such that no two paths share an endpoint. It is clear that this is possible. We will orient each path separately in the same direction, so we may WLOG shorten each path to an edge between the endpoints. As degrees are still all odd, every vertex has odd degree in the 1-forest. Hence, this decomposition of the 1-forest into edges and reduction results in a perfect matching on the vertices. The 2-forest, after reduction, consists of a partial matching on the vertices. Thus, our graph is now a union of disjoint paths whose edges are labeled $1,2,1,2,\ldots,2,1$, cycles whose edges are labeled $1,2,1,2\ldots,1,2$, and edges that are now labeled by both 1 and 2. It is easy to orient each of these; just orient the 1s in one direction and the 2s in the other. Hence, we are done.

That is exactly my solution,but you can also have cycles going 1,2,1.... but is the same. Edit:You have that case.

Wait, maybe I'm wrong, but if you always have more roads entering than exiting, this can't be possible... unless it's positive difference?

How is it possible to have a positive difference in each vertex when the sum of all differences is 0?

@above Sum of all differences is $0$, but sum of all positive differences could be anything.

Let $G$ be the undirected graph of cities and roads, where the edges have weight $1$ or $2$. We wish to direct this graph so that the difference of the indegree and outdegree is $1$ at every vertex. We actually will prove the statement where $G$ can be a multigraph (we need to strengthen the hypothesis for the induction-esque proof to work), Suppose $v$ is a vertex such that there are two distinct edges $va$ and $vb$ with the same weight. Let $G'$ be the graph with edges $va$ and $vb$ removed, and an edge from $a$ to $b$ added with the same weight as the removed edges. If $G'$ can be directed, it is easy to see that $G$ can, just direct all the edges besides the $va$ and $vb$ ones that were removed as they were in $G'$, and then direct $a\to v$ and $v\to b$ if we had $a\to b$ in $G'$, and flip all arrows if $b\to a$. Thus, we can keep doing this reduction until we get a graph with at most one edge of weight $1$ incident to it, and at most one edge of weight $2$. By the above argument, it suffices to solve the problem in this case. However, here it is not hard to see that the only possibility for $G$ is the disjoint union of path graphs where the edges alternate and start and end at $1$, and alternating cycles. It is quite easy to direct these so that the indegree-outdegree differences are all $1$, as desired.

Call a vertex $v$ balanced if absolute difference in capacity for in/out degrees is at most 1. Colour edges with weight $1$ red and those with weight $2$ blue. First delete all monochromatic cycles, by orienting them either way. Now consider two edges $\overrightarrow{uv}, \overrightarrow{wv}$ of the same colour passing through a vertex $v$. Delete them and draw an edge of the same colour between $u$ and $w$. The orientation of this edge will define the orientation we would have picked for both $\overrightarrow{uv}, \overrightarrow{wv}$. Continuing these processes we reach a stage where neither could be performed any further. Thus the red edges form an acyclic graph with no red-degree $\ge 2$. Same for blue edges. Thus we get two matchings, one of red edges and other of blue edges that we need to orient. Now a vertex will always have a red edge by the oddness of capacity sum. Start with a vertex, going along the red edge; then along the blue edge and so on. It is clear that by doing so, we get a path with all vertices in it having no further edges, and each being balanced within the path. Removing this path, we may induct down on the number of vertices. Done!

Finally finished! This is a really nice combinatorial problem. Here's a collaborative solution with Poker-Face which took us a really long time. The idea of the following solution is basically breaking things apart, and then building things apart back. USA TST 2011 #02 wrote: In the nation of Onewaynia, certain pairs of cities are connected by roads. Every road connects exactly two cities (roads are allowed to cross each other, e.g., via bridges). Some roads have a traffic capacity of 1 unit and other roads have a traffic capacity of 2 units. However, on every road, traffic is only allowed to travel in one direction. It is known that for every city, the sum of the capacities of the roads connected to it is always odd. The transportation minister needs to assign a direction to every road. Prove that he can do it in such a way that for every city, the difference between the sum of the capacities of roads entering the city and the sum of the capacities of roads leaving the city is always exactly one. To solve this problem, we first color all the roads of capacity 1 unit as red and color all the roads of capacity 2 units as blue and deal the problem in the graph theory way, that is, let the cities be the vertex of graph $G$, and two vertex are connected by an edge if and only if there is a road connecting two cities. Before assigning the direction of the graph, we want to know more from the structure of the graph itself. Notice that the initial graph $G$ satisfies the fact that all of its vertex has odd degree. Lemma 01. (Trivial fact) There are an even number of vertex in graph $G$. Proof. Handshake lemma gives us \[ \sum_{v \in G} d(v) = 2E \]as all $d(v)$ is odd, then we must have an even number of vertex. So, we will introduce an algorithm that didn't change the property of the graph, where all of its vertex have odd degrees. Name a red path if the path consists of only red edges and name a Consider a red path $A_1 \to A_2 \to \dots \to A_N$, and transform it to $A_1 \to A_N$. This preserves the parity of every vertex of the graph $G$. Now, we want to minimize the number of red edge and blue edge in graph $G$. Using the algorithm above, we can ensure that every vertex has at most $1$ red edge and $1$ blue edge. Notice that every red edge gives each of its endpoints 1 degree and every blue edge give each of its endpoints 2 degree by definition. Since the degree of all the vertex are odd, then all must be connected by exactly 1 red edge. We will consider each connected components of the graph. There could now be 2 possibilities: Either it is a chain or a cycle. Since there are an even number of vertex, and each vertex must have exactly 1 red edge.Then each chain or cycle has even length. After reducing the graph by the previous algorithm, we will now prove that this final state of the reduced graph can be assigned by arrows to satisfy the problem's condition. Denote $\to$ as the red edge and $\Rightarrow$ as the blue edge. We assign the arrow as : $A_1 \to A_2 \Rightarrow A_3 \to A_4 \Rightarrow \dots A_{2n - 1} \to A_{2n} $. One could verify easily that this works as the chain or cycle has even length. Now, we will prove that any initial graph $G$ can be assigned such arrows. Now, by reversing the path that we used to reduce graph $G$, we will prove that we can restore back graph $G$, but now with arrows. Notice that we could build up from $A_1 \to A_N$, to $A_1 \to A_2 \to A_3 \to \dots A_n$ (the direction is the same as the arrows here). Notice that the number of ins and outs of each route remains the same, and therefore since the initial "reduced" graph satisfy the condition of the problem. The "restored" initial graph must also satisfy the condition of the problem. We are hence finished.

Probably nothing new but here it is... 1) Delete any cycles that are exclusively composed of roads of one capacity at any instance. Also, if two cities are connected by two roads with the same capacity at any point, delete both roads. (Does not happen in the initial stage but may happen after step 2 that is described below.) 2) If any vertex has two roads that are of the same capacity, delete both and replace it with one road connecting the two end points of the original roads. This process is finite because each time, you are deleting roads. Now, we have a graph without cycles and no vertex has more than 1 road of given capacity. Note that if two roads are both connected with a road of capacity 1 and 2, then they cannot be connected to any other vertex and they themselves become an isolated system. Notice that every connected component of the graph that we have now is alternating between blue and red. Just direct the roads such that they all point to the same direction within each connected component.

a solution by Fouad Al-mouine We will approach the solution by strong induction, i.e: suppose for every $k$ points in the plane the minister can find a way to assign the directions (where $k \in {1,2,...,n-1}$). First of all, assume there are $n$ points, if the graph $G$ is not connected then we are done by strong induction. So suppose that $G$ is connected, in other words there exist a path (or a cycle) in $G$. Notice that if there exist two segments $AB,AC$ that have the same capacity ($1$ or $2$) and share a common point ($A$), then ignore the point $A$ and segments $AB,AC$ for a while and connect points $B,C$, but this process keeps the sum of the segments (roads) capacities with the same parity (i.e: odd) so we are left with $n-1$ points and we can apply the induction hypothesis, when we re-invite segments $AB,AC$ and delete $BC$ after the induction we get that the $G$ satisfies the conditions and we are done. Therefore suppose that there don't exist any segments with the same capacity that share a common point, combined with the result that $G$ is connected (it forms a path or a cycle), we get that there are no forests in $G$ thus it's a chain from $1,2,1,2,\cdots$ that form a cycle or a path, clearly the minister can assign directions into this graph that satisfies the conditions by considering a vector that starts from the very first point and continues till the end.

Represent the problem as an undirected graph where cities are vertices and roads are edges which have capacities $1$ or $2.$ We will prove that we can direct the edges so that the difference between in capacities and out capacities of each vertex is $1$ Consider all the cycles with all edges having the same capacity in the graph. Direct all the edges in each cycle the same way. This will add $0$ to the difference of each vertex. Next, we split the remaining vertices into paths. Consider all paths that pass through a vertex $A.$ Since there is an odd number of edges with capacity $1,$ there must be exactly one path that passes through $A$ at one edge with capacity $1.$ Call this path $P.$ Then, we make all other paths that pass through $A$ at an edge with capacity $1$ pass through $A$ so that both edges it passes through that are connected to $A$ have capacity $1.$ If $A$ has an even number of edges with capacity $2,$ $P$ ends at $A.$ If $A$ has an odd number of edges with capacity $2,$ $P$ continues along one of the edges with capacity $2.$ Then, we make all other paths that pass through $A$ at an edge with capacity $2$ pass through $A$ so that both edges it passes through that are connected to $A$ have capacity $2.$ Do this for all the vertices so that all the edges are part of a path. Now we direct all the edges in a path the same way. Clearly, all the paths must end at an edge with capacity $1,$ so at the vertex that a path ends at the difference will be $1.$ At all the vertices that a path does not end at, a path passes through it at one edge of capacity of capacity $1$ and one edge of capacity $2,$ so this path clearly adds $1$ to the difference, and by our construction all the other paths add $0$ to the difference. Thus, all the vertices will have difference $1,$ as desired.

yunseo wrote: Probably nothing new but here it is... Let Andrew be the transportation minister. Andrew designates paths of consecutive roads with uniform capacities to be highways in the following manner: Start with each road as unique highway. Whenever two highways share the same traffic capacity and share a city as a terminus, combine them at that city. We claim that there exists a direction that Andrew can assign each highway (moving from one end to the other) so that the condition is satisfied. Notice that if a city is not a terminus for any highway of capacity $1$, it has an even number of roads of capacity $1$ connected to it, impossible. Furthermore, if a highway passes through a city (it is not one of its termini), the net contribution to the value of the in capacity minus the out capacity is zero. Hence we can delete all the normal roads and only have one highway connecting its two termini (and only those cities). Now clearly each city has at most two highways connecting to it, hence the graph must be made up of cycles and paths, each with alternating highways of capacity $1$ and $2$. No path can have a highway with capacity $2$ at its very end, since then the furthest city would not be the terminus of any highway of capacity $1$. Now simply setting a uniform direction for each cycle and each path since each city will have one highway of capacity $1$ going in/out and one highway of capacity $2$ going in the opposite direction, or just one highway of capacity $1$ connected to it, hence an absolute difference of $1$ for the in capacity and out capacity. $\blacksquare$

We will simplify the graph as follows, assuming that there exist two edges with the same capacity $c$ that are adjacent to each other, say $(u,v)$ and $(v,w)$: we delete the edges $(u,v)$ and $(v,w)$, and, in addition, If the edge $(u,w)$ is not present, then add on the edge $(u,w)$; If the edge $(u,w)$ is present and has the same capacity $c$, then delete $(u,w)$ as well; If the edge $(u,w)$ is present and has a different capacity, then change the capacity of $(u,w)$ to 1. It's easy to check that a valid assignment of edge directions after this operation can be extended to a valid assignment of directions in the original graph. Furthermore, the number of edges in the graph is decreased by at least 1. Therefore, repeating this operation, we arrive at a graph where each vertex is incident to at most one edge with each capacity. It's obvious that such a graph can be directed as desired.

Take a directed graph $G$ with vertices $v_1, v_2 \dots, v_n,$ and let $w(v_iv_j)$ denote the weight of edge $v_iv_j,$ (where $v_iv_j$ is a directed edge from $v_i$ to $v_j)$. For every edge, we assign weights depending on the amount of traffic. We proceed by induction. The condition is easily satisfied for $n = 4.$ Now, assume $n-1$ works.Then, we can do the following process (repeatedly): Take any edge, $v_iv_j,$ and then some other edge $v_jv_l$ if $w(v_iv_l) = w(v_iv_j).$ Then, delete both of those edges and replace it with $v_iv_l.$ It is easy to see that this still preserves the even/oddness property that $G$ has to have. If there exist no such edges, take an edge $v_iv_l$ and any $v_j,$ such that the first step is possible. finally, if there is a vertex that is disconnected from the rest of graph, delete it, and now we have a graph of $n-1$ vertices, and by the induction, we are done. [asy][asy] unitsize(36); dot((-2,-0.5)); label("$v_{i-1}$", (-2,-0.5), N); dot((4,0)); label("$v_{l+1}$", (4,0), N); dot((0,0)); label("$v_i$", (0,0), N); dot((2,0)); label("$v_l$", (2,0), N); dot((1, -2)); label("$v_j$", (1,-2), S); draw((0,0)--(1,-2), MidArrow); draw((1,-2)--(2,0), MidArrow); draw((0,0)--(2,0), grey+dashed+linewidth(1)); draw((-2,-0.5)--(0,0)); draw((4,0)--(2,0)); [/asy][/asy]

Take the obvious graph theory interpretation with edges weighted 1 or 2. We claim for any multigraph $G$ we can orient it to satisfy the condition. Induct on the number of edges $E$. Suppose some $v\in G$ has two edges $va$ and $vb$ of equal weight. Let $G'$ be the multigraph with these deleted, but edge $ab$ added. (This is why multigraph is necessary; $ab$ could already exist.) One less edge, so orient it by induction. Now in oriented $G'$, suppose $ab$ is oriented $\vec{ab}$. Replace $\vec{ab}$ with $\vec{av}$ and $\vec{vb}$. This does not change $\sum \text{out} - \sum \text{in}$ of any vertex, and sum of weights of edges connected to $v$ decreases by 2, not changing parity. The above operation may cause buildups of multiple edges of the same weight between two vertices. Choose any two and orient them oppositely, and orient the remaining multigraph by induction. The above process finishes, unless for any $v$ there don't exist $va$ and $vb$ of same weight. So now assume every vertex of $G$ is in at most one weight 1 edge and at most one weight 2 edge. Now, if there are vertices $v,w$ with weight 1 and 2 edge between them, then neither can connect to any edge by assumption about $G$. So they are isolated, and orient them oppositely. So $G$ is not a multigraph anymore. Now it's easy to see the only possibilities are unions of alternating 1 and 2 cycles, and path graphs starting and ending at 1. Easy to orient these, done.

Here is a weird solution. Call the valency of a vertex its outdegree minus indegree. We first make two optimizations: 1. If a cycle only consist of edges of the same weight, we can remove it. When we add it, the indegree minus outdegree will not be changed. 2. Consider the minimal counterexample. If the set of 2-edges contain a cherry, say $w_{a,b}=w_{a,c}=2$. By our above optimization, $w_{b,c}\ne 2$. We know the graph with edges $ab, ac$ removed and $w_{b,c}\rightarrow 2-w_{b,c}$ has a way of orienting edges. Say $b\rightarrow c$, then I can make $c\rightarrow b, b\rightarrow a, a\rightarrow c$. Therefore, the set of 2-edges is a matching and the set of 1-edges is a forest. We first orient the 1-edges, and it suffices to do so such that for each pair of vertices $(a,b)$ connected with a 2-edge, one of them has valency -1 and the other has valency 1. We first orient each tree such that except for the root, the indegree from the children is equal to the the outdegree from the children. This means we can reverse all directions of the edges of a subtree that is NOT the root. We employ the following process: Step 1: If one of $(a,b)$ is root, say $a$, then we can reverse all edges of $a$'s subtree. Step 2: Now for all the $(a,b)$ remaining, neither is a root of a tree. We employ the following process of reversing a cherry, namely $a\rightarrow b\rightarrow c$. If $c$ is not in a matching, or if $c$ is in a matching and needs to be fixed, this is totally viable. Otherwise, I can repeat this process. Eventually I either bump into a vertex not in a matching, or I bump into a cycle. I claim we cannot bump into a cycle. Say the pairs are $a_i, b_i$, and the two endpoints of the cherries are $a_i$ and $b_{i+1}$, where $b_{n+1}=b_1$. Let $V(m)$ denote the valency of vertex $m$. Assume for the sake of contradiction $V(a_1)+V(b_1)\ne 0$ but $V(a_i)+V(b_i)=0$ for all other $i$. Also note $V(a_i)+V(b_{i+1})=0$, so summing gives $V(a_1)+V(b_1)=0$, contradiction. So we bump into a vertex not in the matching. Now, flip each $a_i\rightarrow p\rightarrow b_{i+1}$ (where arrows means pointing to same direction, not necessarily outwards), and we would be good. This process strictly decreases the number of matching pairs that needs to be taken care of, so we are good.

This problem is so dumb ahaha totally wasn't stuck on it I assume that we are allowed to have multiple roads connecting the same two cities. Of course, proving this version of the problem suffices to prove the version where only one road can connect two given cities. Consider the obvious graph theory interpretation, letting Onewaynia be the graph $G$. Let $v_1-v_2$ and $v_1=v_2$ mean that $v_1,v_2$ are connected with a road of capacity one or two. We make the following assumptions, which don't make the problem any "easier": $G$ is connected, since if it isn't we can just consider each connected subgraph separately. If we have some vertices $v_1-v_2-v_3$ (not necessarily distinct), then replace the roads between $v_1,v_2$ and $v_2,v_3$ with a road of capacity $1$ connecting $v_1$ and $v_3$: then $v_1 \to v_3$ corresponds to $v_1 \to v_2 \to v_3$ and the other way around too, so this only makes the problem harder. As such, we can assume that every vertex has at most one road of capacity $1$ connected to it. With the same logic, we can assume that every vertex has at most one road of capacity $2$ connected to it. With these three assumptions combined, it follows that it suffices to prove the case in which $G$ is of the form $$v_1-v_2=v_3-v_4=\cdots=v_{k-1}-v_k,$$where all $v_1,\ldots,v_{k-1}$ are distinct but we allow $v_k=v_1$. Then just make the road between $v_i$ and $v_{i-1}$ point towards $v_{i-1}$ for $1\leq i \leq k$, which clearly works. $\blacksquare$

Let G be the graph of cities as vertices and roads as edges. We will prove this problem with induction on the number of edges of our graph G. Let $d_1(v)$ and $d_2(v)$ denote the degrees of v considering the subgraphs of only capacity 1 edges and capacity 2 edges respectively. Base cases: $d_1(v) < 2$, $d_2(v) < 2$ for all vertices v The given odd degree condition forces $d_1(v) = 1$ for all v, and $1 \leq d(v) \leq 2$ for all vertices v, so the overall graph will be a set of connected components, with each one being either a path or a cycle. Furthermore, it is easy to see that in each path/cycle, the edges alternate between capacity 1 and 2. If our component is a path, just traverse from the starting leaf to the end leaf, directing the edges in the direction you traverse. If its a cycle, do the same from an arbitrary vertex; due to the alternating between capacity 1 and 2, both of these methods clearly work. We now induct on the number of edges. All graphs with $<=1$ edge are obviously in our base case. Assume now that all graphs with $k-1$ edges work. Consider an arbitrary graph G with $k$ vertices that is not in our base cases. Then, there exists some vertex v with $d_1(v) \geq 2$ or $d_2(v) \geq 2$. Consider two edges $uv, vw$ with the same capacity. Consider replacing them with $uw$. This makes a graph with $k-1$ edges satisfying the same degree conditions, and hence we can find a way to direct the edges to satisfy our desired difference condition. If we have $u \rightarrow w$, we could have $u \rightarrow v \rightarrow w$ in the original graph and direct all other edges as how we would in the replaced graph, keeping all given conditions and desired outcomes the same; likewise for the other case. Hence, we are done. Q.E.D.

Solution: Let us rephrase the problem in equivalent graph theory language. Given a graph $H$ and the orientation of its edges, define $p_H(u)=\deg_+u-\deg_-u$ for $u\in V(H)$. Let $G$ and $G'$ be two simple graphs on vertex set $V$. Every vertex has an odd degree in $G$. Prove that it is possible to give orientations to edges of $G$ and $G'$, such that for each vertex $v\in V$, $\mid p_G(v)+2p_{G'}(v)\mid =1$. We start the proof with the following lemma. Lemma: Let $H$ be a simple graph. It is possible to sort its odd vertices into pairs, such that any pair $\{u,v\}$ are connected by a path. In addition, all the paths connecting the pairs do not share edges. We call this pairing a good pairing. Proof of the lemma: In each connected component of $H$, there are an even number of odd vertices. Hence if there is an odd vertex, we can find another odd vertex in the same connected component. Take these two as a pair, obviously there is a path connecting them. We delete the edges of the path, it does not change the parity of the other vertices. Continue doing so and we are done. $\blacksquare.$ Notice that after we give a good pairing of odd vertices of a graph, we can give the orientation of the path at the same direction. After deleting these paths, all vertices would have even degrees, due to Euler Circuit we can give the rest of the orientation such that every vertex have the same degree in as degree out. Thus we can replace $G$ and $G'$ with $D$ and $D'$, satisfying each vertex in $D$ has degree $1$ and each vertex in $D'$ has degree at most $1$. We only have to give orientation of $D$, $D'$ such that $\mid p_D(v)+2p_{D'}(v)\mid =1$ $(\star)$ Consider graph $K:=D+D'$ (count the double edges). Color the edges from $D$ red and the edges from $D'$ blue. Each connected component is either a even cycle with red-blue alternating edges, or a red-blue alternating path starting and ending with red edges. It is trivial to give the orientation to these edges so that $(\star)$ holds. Thus we are done!

Somehow this was pretty difficult, though the solution feels very intuitive after you get it. The idea is to make modifications to the graph as follows: for any paths $v_1v_2$ and $v_2v_3$ of equal capacity, we can replace it with $v_1v_3$. This is as we can point the paths $v_1v_2$ and $v_2v_3$ in that direction, so that removing them does not change the net capacity at $V_2$, and the net capacity at $v_1$ and $v_3$ does not change either; we can point the path $v_1 \to v_2 \to v_3$ in the other direction if necessary. So we can reduce the problem to the case where every vertex has at most two edges from it, one of each capacity. We may assume the graph is connected, so it follows that the only possibilities are paths and cycles with alternating capacity, which are easy to orient.

Call a road with capacity $1$ a $1$-road and define a $2$-road similar. Generalize to the case of cities having multiple roads between them. Attach a positive $n$ to the city in the direction a road is pointing and a $-n$ to the other city. Then, it remains to show that it is possible to choose road directions such that the sum of the numbers attached to a number is either $1$ or $-1$. Claim: If a city has two roads of the same capacity, it is possible to merge them into one road. Proof. Suppose that city $a$ has two $n$-roads that connect to cities $i$ and $j$, possibly equivalent. By ensuring the direction of the two roads are inverted such that their net effect on the sum of $a$ is $0$, this becomes equivalent to one $n$-road between $i$ and $j$. $\blacksquare$ Evidently, an $n$-road from one city to itself has zero net effect and be cancelled out. Then, repeat this until no city has two roads of the same capacity. As such, each city has one $1$-road and potentially a $2$-road, and thus has at most degree $2$. Claim: We can choose directions on this configuration. Proof. The directed graph of the roads dissects into a collection of paths and cycles that alternate between $2$-roads and $1$-roads. By alternating the direction of the roads when going along the cycle or path, it is possible to have each sum of a city in the path or cycle be $1$ or $-1$. $\blacksquare$ Note that this solution generalizes to the case of having $n$-roads and $n+1$-roads.

holy this is a GREAT problem, kind of underwhelming after solving though Call the roads with 1 and 2 capacity small and big roads. Note that if there's two roads out of v to u and w of the same size, we can orient the roads to become $u\rightarrow v\rightarrow w$ and so we can remove those two roads and keep it as $u\to w$ since there's no effect. By the odd capacity/size, there's exactly one small road and at most one big road; if there's both then orient the small road in same direction as big road (so that the difference is 1), and if there's only small road then anything suffices, done.

Color blue the edges of capacity $1$ and red the rest. We make the following reductions in order (where by deleting, we mean orienting the same way when inducting backwards): Firstly, delete all monochromatic cycles. Thus, the graph induced by the blue edges is a forest. Consider a red edge in some blue tree. Then, we can replace it with a blue edge and delete the blue path that connects its ends from the tree. Consider red cycles of blue trees (collapse the trees into nodes and view usual red cycles). Then, we can replace all red edges with blue, deleting all blue paths inside the trees. When the dust settles, we're left with a blue forest connected on a red tree (i.e. a red tree with a blue tree put in every node). It suffices to orient a blue tree now and connect all red edges one by one. To this end, do an algorithm similar to DFS, changing color when coming back to another path (or induct on a construction for a branch, which is direct).

Now take n cities with the roads w/o direction. Then take a vertex $x$. It will have some 2unit roads and some 1unit roads then say two vertices $v,w $ are there such that $vx, wx$ are both roads having the same traffic units. So in stead of these two roads you can consider a singular vertex which is $vw$. continue this process on $x$ till no longer possible. In this state $x$ will have either have a singular 1unit road or 1 1unit and 1 2unit road. Now repeat this process with all the other vertices. The resulting configuration has cities such that all cities have at most 2 roads. Now just give the some edge some direction and continue to keep the condition in check, and this process must terminate as each city has at most 2 roads so we either are in a path or a cycle. Either way the process terminates and now take one of the undirected roads give it a direction(we have to take a new one as in this process of removal some components may disconnect) and continue till we have given directions to all the roads and we just have to undo the removal of edges which is a simple task. $QED$ PS: very nice problem it shows there are other ways to remove edges rather than only the standard removal i really liked the problem.

We first rephrase the problem using graph theory, and suppose we have two edges $AB$ and $AC$ from vertex $A$ of the same capacity. The key observation is that we can simply replace both edges with a single edge $BC$ (possible creating a multigraph) with the same capacity. We can continue this process until it terminates, and if we can sucessfully direct the resulting graph, we can "undo" our process by taking each directed edge (in reverse order of this process) $\overrightarrow{BC}$ and replace it with $\overrightarrow{BA}$ and $\overrightarrow{AC}$. Notice our process works as the parity of the capacity sum and the desired absolute differences for each vertex is invariant. Thus it suffices to show the result for multigraphs (without self-loops) with each vertex incident on either one edge with capacity 1 or two edges with capacities 1 and 2. With each vertex having degree 1 or 2, the resulting graph is a collection of (undirected) cycles and paths. We simply assign directions to each edge by making each cycle/path a directed cycle/path, which works as each absolute difference would simply be $|\pm 1|$ or $|\pm (1-2)|$. $\blacksquare$