How to direct the edges of this graph?

123 Views Asked by At

I know from here that every planar bipartite graph with $n$ vertices, has at most $2n-4$ edges.

I want to prove that we can direct the edges of this graph such that each vertex has an outer degree at most 2.

My idea is to prove by induction, we know that $\sum_{v \in V(G)} d(v)\leq 4n-8$ so we have a vertex like $u$ with a degree at most 3. If $d(u)\leq 2$ then we can omit $u$ and use induction easily, but I do not know what to do in case that $d(v)\geq 3$ for all $v\in V(G)$.

1

There are 1 best solutions below

0
On

There may be an easier way to solve this that doesn't rely on a powerful theorem, but here's a method. Let $G$ be a planar bipartite graph, and observe that any subgraph $H$ of $G$ is also bipartite and planar. By your inequality, and the handshaking lemma, we always have that, for any subgraph $H$:

$|E(H)|/ (|V(H)| - 1) \leq (2n-4)/(n-1) \leq 2$.

Hence, by the generalised Nash Williams Theorem (Wikipedia - Nash Williams Theorem) we can decompose the edge set of $G$ into two forests (a forest is just a graph where each connected component is a tree).

{You may be able to prove the above bit directly without appealing to Nash Williams.}

Now we consider the two forests we have obtained. Let $T$ be a tree of one of the forests, and pick a vertex $r$ to be the root of $T$. Orient every edge of $T$ to point 'towards' the root. So if $u$ and $v$ are adjacent in $T$, the directed edge $uv$ should go from the vertex which is further from $r$, to the one which is closer to $r$. In this orientation, each vertex of $T$ can have high in-degree, but will only have out-degree 1 in $T$. We do this same thing for every tree of both forests. Each vertex of $G$ lies in 1 tree of each of 2 forests, and so has out-degree at most 2, as desired.