1
$\begingroup$

I was working through a few problem sets and came across this question

Suppose there is a connected planar simple graph $G$ with $v$ vertices such that all its regions are triangles (a cycle consisting of three edges).

Question 1: Into how many regions does a representation of the Planar Graph $G$ Split the plane?

Incase of this question, since all the degrees of regions are said to be 3, we can say $2e=3r$. I substituted this value into the Euler equation, $v-e+r=2$ and got my final answeras $2(v+2)$.

Question 2: Suppose the vertices of the planar graph G are colored in three colors. A region is called to be tricolored (or bicolored) if its vertices are colored in exactly three (or two) different colors. Similarly, a monocolored region is the one with all its vertices colored in exactly one color. Prove that the number of tricolored regions is always even no matter how the vertices are colored.

(Hint: If you place a new vertex inside a region (triangle) of G and connect it with all vertices of that region, then all regions are still triangles and the parity of the total number of regions stays the same.)

This question seemed very straight-forward to me on account of my previous answer. Since I derived the value $r = 2(v+2)$ which would always remaining even while incrementing $v$. I don't really understand the point of the Hint or maybe what exactly we have to prove here.

Any help with regard to the same would be appreciated. Thanks!

$\endgroup$
  • $\begingroup$ I edited your question to remove the first part, since the Stack Exchange format doesn't work well with multiple distinct questions in a post, and "Please check my answer"-type questions are off-topic on this particular site. If you want to ask a question about that exercise that's more conceptual than "was my answer right?" then please do post it as a new question. $\endgroup$ – David Richerby Nov 29 '18 at 18:21
  • $\begingroup$ @DavidRicherby The 2 questions are sub questions related to the main question. The answer of the first question is usually related to the answer of the second question. I've asked questions of a similar fashion on some on stackoverflow/ mathstackexchange etc. Don't the same rules apply here? $\endgroup$ – Gary Andrews30 Nov 29 '18 at 18:23
  • $\begingroup$ Different sites have different policies, and "Please check my answer" is off-topic here, even if it's on-topic elsewhere. But I agree that my edit completely mangled your question. Give me a second and I'll try to fix that. $\endgroup$ – David Richerby Nov 29 '18 at 18:26
  • $\begingroup$ @DavidRicherby I would much appreciate it if you make a suggestion instead of making a direct edit as you seem to have not understood the question and your prior edit completely changed my question and I was forced with the inconvenience of editing it again. Thanks $\endgroup$ – Gary Andrews30 Nov 29 '18 at 18:28
  • $\begingroup$ I'm sorry I messed up. I'd already made my second edit before the system showed me your comment asking me not to. There is a "roll back" link in the edit history you can use to very quickly undo an edit; you can get to the history by clicking the "edited x minutes ago" link. $\endgroup$ – David Richerby Nov 29 '18 at 18:32
0
$\begingroup$

Since all the degrees of regions are said to be 3, we can say $2e=3r$. I substituted this value into the Euler equation, $v-e+r=2$ and got my final answer as $2(v+2)$.

The final answer should be $2(v-2)$.

Since I derived the value $r=2(v-2)$ which would always remaining even while incrementing $v$.

You are right that $r$, the number of regions will always remain even since $r=2(v-2)$. However, question 2 is asking you to prove "the number of tricolored regions is always even no matter how the vertices are colored.".

I don't really understand the point of the Hint or maybe what exactly we have to prove here.

The hint is meant to give you a clue how to reduce the number of vertices. The proof (or my proof) is quite easy and direct once you know it. I will let you figure out your proof.

$\endgroup$

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.