# Prove that for every planar graph, there is a partition $V = V_1 \cup V_2 \cup V_3$ such that the graphs with those are acyclic

Prove that for every planar graph $G = (V,E)$ with $|V| \geq 3$ there is a partition of V to $V = V_1 \cup V_2 \cup V_3$ such that $V_1 \cap V_2, V_1 \cap V_3, V_2 \cap V_3 = \emptyset$, where for all $1 \leq i \leq 3$ the graph that is formed by $V_i$ is acyclic.

I am still not able to comprehend the "tricks" that are used to solve Graph-Theory questions, and I am having a tough time with them. When I read the question, I said this:

If $G$ is planar, then all subgraphs of it are planar. That means that $V_i$ is planar for all $1 \leq i \leq 3$.

But I still can not get a direction on how to prove that it is acyclic. Any direction would be appreciated.

• Did you try an induction on the size of $V$? Something like $|V|=3$ it's easy. suppose it true for $|V|=n$. For $|V|=n+1$ take out one of the vertices and suppose by the absurd that for every partition you obtain if you append the vertex it form a cycle. Look at the neighbour of this vertex and show that it contradict the planar assumption. I didn't try but it seems to me that it can works. – wece Jun 6 '13 at 9:25
• Trying it, thanks. – TheNotMe Jun 6 '13 at 12:29
• @wece I wasn't able to arrive to a contradiction. Any help will be appreciated. – TheNotMe Jun 6 '13 at 15:02

Let $P(n)$ be: for every planar graph $G = (V,E)$ with $|V| = n$ there is a partition of V to $V = V_1 \cup V_2 \cup V_3$ such that $V_1 \cap V_2, V_1 \cap V_3, V_2 \cap V_3 = \emptyset$, where for all $1 \leq i \leq 3$ the graph that is formed by $V_i$ is acyclic.

We call good partition the partitions satisfying the property.

$P(3)$ is trivial. $\{v_1\},\{v_2\},\{v_3\}$ is a good partition.

Suppose that $P(n)$ is true and let us show that $P(n+1)$ hold.

$V=\{v_1,\dots,v_{n+1}\}$, let $\bar{V}^i$ be the set $\{v_1,\dots,v_{i-1},v_{i+1},\dots,v_{n+1}\}$ by hypothesis there is a good partition of $\bar{V}^i$. Three cases:

1. there exists $i$ such that there exists a good partition of $\bar{V}^i$ such that $\forall (v_{i},v)\in E, v\notin V_1$ then $V_1\cup\{v_{i}\},V_2,V_3$ is a partition of $V$ satifying $P(n+1)$.

2. or, there exists $i$ such that there exists a good partition of $\bar{V}^i$ such that $\exists v\in V_1,(v_{i},v)\in E$ and $\forall (v_{i},v')\in E,v\neq v'\implies v'\notin V_1$ then $V_1\cup\{v_{i}\},V_2,V_3$ is a partition of $V$ satifying $P(n+1)$.

3. Or, for all $i$ and for all good partitions of $\bar{V}^i$ there are at least two neighbour of $v_{i}$ in each set $V_j$. Hence the degree of each vertices is at least 6. But: see last corollary of this page : "Every finite, simple, planar graph has a vertex of degree less than 6" contradiction with "G" is planar.

• I was hopping for a simpler proof, but assuming you knew that every planar graph had a vertex of degree less than 6, I think it's understandable. – wece Jun 6 '13 at 17:08
• Clear, straightforward and simple. Thanks alot! – TheNotMe Jun 8 '13 at 9:04

You know that your graph is planar therefore we know from the Euler equation n-e+f=2 n-vertices e-edges and f-faces, that $|E| \leq 3|V|-6 \Rightarrow 2|E| \leq 6|V|-12 \Rightarrow$ Where has to be a v s.t: $d(v) \leq 5$ in G. This is the first conclusion.

Now for n=3 you van clearly see you can decompose into three disjoint vertice sets. Induction claim: suppose that for every k < n It holds true that any k vertex planar graph can be decomposed $V = V_1 \cup V_2 \cup V_3$ where each $V_i$ is acyclic.

Look at k=n, you clearly know where is v s.t: $d(v) \leq 5$ look at V'=V-{v} this is still a planar graph with n-1 vertices $\Rightarrow$ where's a decomposition of this graph $V' = V'_1 \cup V'_2 \cup V'_3$ where each $V'_i$ is acyclic. Now let's add back the v we removed notice that if it closes a cycle it must have 2 edges going into one of the $V'_i$-s but by the pegion hole principle we have 5 edges to distribute between 3 groups so it has one edge exactly going into some group, which cannot close a cycle so add it to that group and here you got the disjoint decomposition.

Wayne Goddard, Acyclic Colorings of Planar Graphs, gives a proof of a stronger result, and a reference to a proof of the result you want. I think the paper is freely available on the web. The earlier paper is G. Chartrand & H.V. Kronk, The point-arboricity of planar graphs, J. London Math. Soc. 44 (1969) 612–616.

• A good search term is "vertex arboricity". – Gerry Myerson Jun 6 '13 at 10:59