1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – wece Jun 6 '13 at 9:25
  • $\begingroup$ Trying it, thanks. $\endgroup$ – TheNotMe Jun 6 '13 at 12:29
  • $\begingroup$ @wece I wasn't able to arrive to a contradiction. Any help will be appreciated. $\endgroup$ – TheNotMe Jun 6 '13 at 15:02
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – wece Jun 6 '13 at 17:08
  • $\begingroup$ Clear, straightforward and simple. Thanks alot! $\endgroup$ – TheNotMe Jun 8 '13 at 9:04
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.