Prove that a finite simple planar graph has an orientation so that every vertex has out-degree at most 3.
Problem
Source: Romania TST 1 2012, Problem 4
Tags: induction, combinatorics proposed, combinatorics
06.05.2012 16:00
We will use the well known fact that every simple planar graph with $n$ vertices has at most $3n-6$ edges. Let begin to orient consecutively the graph $G$. If an edge $\{u,v\} \in E(G)$ we choose arbitrary the direction of this edge $(u,v)$ or $(v,u)$ complying the rule every vertex to has out-degree at most $3$. We will stop in two cases: 1. There are no remaining edges to be oriented. In this case we are done. 2. We can not orient any of the remaining non oriented edges obeying the rule out-degrees to be at most $3$. Let $\{a,b\} \in E(G)$ is yet non oriented. Denote by $d^o(a)$ the out-degree of $a$. Then $d^o(a)=3$, because if $d^o(a)<3$ we can continue the process and orient $\{a,b\}$ as $(a,b)$. Let denote by $O(a)$ all three vertices $v_1,v_2,v_3$ corresponding to the oriented edges $(a,v_1),(a,v_2),(a,v_3)$. More generally, if $V \subset V(G)$, denote by $O(V)$ all $u \in G$ such that there exists $v\in V$ for which $(v,u)$ is oriented in such way. Let now $O^2(a)=O(O(a)),\ldots, O^n(a)=O(O^{n-1}(a))$. Assume that for some $n$, there exists $v \in O^n(a)$ such that $d^o(v) < 3$. Then there will be a sequence of oriented edges $(a,v_1),(v_1,v_2),(v_2,v_3),\ldots,(v_{\ell}, v) $. Then we can change these oriented edges with their opposite derections, i.e. $(v_1,a),(v_2,v_1),(v_3,v_2),\ldots,(v, v_{\ell})$ and in that way the new oriented graph will have $d^o(a)=2$, so we can continue the above process by orienting $\{a,b\}$ as $(a,b)$. Let now assume that $\forall n, \, \forall v \in O^n(a),\, d^o(v)=3$. Denote by $G_1$ the oriented graph with $V(G_1)= \{a\} \cup \bigcup_{i=1}^{\infty} O^i(a) $ and $E(G_1)$ be all oriented edges connecting vertices of $V(G_1)$. Obviously $G_1$ is a planar graph as a subgraph of $G$. With current assumptions $\forall v \in V(G_1),\, d^o_{G_1}(v)=3$. This means $E(G_1)=3 V(G_1)$. Thus $G_1$ is not a planar graph, contradiction. Thus we proved that with the described process we could comply the rule out-degrees to be at most $3$ untill there are no non-oriented edges.
11.05.2012 06:51
Oops, I thought of dgrozev's approach but didn't see a way to complete the solution. Anyways, I think this inductive solution works:
27.08.2015 22:29
This is easier: Let $G$ be a simple planar graph. For a vertex $v$, denote $\deg^{\omega}(v)$ as its out-degree. Given an embedding of $G$, choose a face of $G$, and let any vertex on that edge be special. Let $S(G)$ be the set of special vertices. We show by induction on $|G|$ that $\deg^{\omega}_{v\in G}(v)\leq 3$ and $\deg^{\omega}_{v\in S(G)}(v) \leq 2$. Clearly, there exists some special vertex $v$ adjacent to at most two other special vertices. Let $G'$ be the subgraph of $G$ formed by removing $v$, and setting as its special vertices the union of the remaining special vertices of $G$ and the neighbors of $v$. By the induction hypothesis, we can orient $G'$ in such a way that $\deg^{\omega}_{v \in G'}(v)\leq 3$ and $\deg^{\omega}_{v \in S(G')}(v) \leq 2$. Now we orient the edges $(v,x)$ between $v$ and its neighbors. If $x \in S$, orient $\overrightarrow{vx}$; otherwise, orient $\overrightarrow{xv}$. This produces the desired orientation, and we are done by induction.
31.08.2015 17:19
It is well known that every planar graph is a subset of a triangulation,from which we have that it has at most $3n-6$ edges.Now,we create a bipartitate graph $F$ beetwen edges and vertices.In one group we have vertices that represent edges and in the other group we have $3$ identical groups of vertices which represent vertices of $G$.An edge is connected with vertex i edge contains that vertex.We have to find a perfect matching that includes all egdes.From here,we procced via Hall's theorem.Assume that it doesn't.Then,we have a set of $k$ edges which cover at most $[k/3]$ vertices,but this means that we have a set of $m$ vertices which has at least $3m$ edges,which is a contradiction.
05.06.2019 06:22
We can use the following hammer (Nash-Williams theorem). https://en.wikipedia.org/wiki/Nash-Williams_theorem It says that if every subset $S \subseteq V(G)$ contains at most $c(|S|-1)$ edges, then we can partition the edges of a graph into $c$ forests. As we know that any subset $S$ of vertices contains at most $3|S|-6$ edges, a planar graph can be partitioned into $3$ forests. For each tree in the forest, pick an arbitrary root and direct all edges in the tree towards the root. Clearly, this construction causes all vertices to have outdegree at most $3$.