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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.