6
$\begingroup$

Let $G=(V,E)$ be a connected simple planar graph whose edges can be colored red and blue so that for any vertices $u,v∈V$, there is a unique path connecting $u$ and $v$ whose edges are all red, and a unique path whose edges are all blue.
Prove that any planar embedding of $G$ has at least $4$ triangular faces (i.e., faces with degree $3$). This count may include the outer (exterior)face.

I found that each edge in this graph is contained in a cycle and each face has at least degree $3$. Also I have the formula that $|V| - |E| + |F| = 2$ and $3|F| \leqslant 2|E|$, but I am not sure how to relate this to the number of triangular faces in the graph.

Can you help me solve this problem?

$\endgroup$
3
$\begingroup$

Here's an approach, can you fill in the details?

  1. Argue that $E = 2V - 2$.
  2. Argue that if $G$ has fewer than $4$ triangular faces, then $2E \geq 4F - 3$
  3. Explain why those two are contradictory
$\endgroup$
  • $\begingroup$ I figured out your second and third steps but I am still wondering how do you get the first equation? I know it must somehow be related to the fact that their are two uniquely colored paths between any two vertices but...Is it like double the edges of a tree because in a tree we have E = V - 1, but then it is not a simple graph... $\endgroup$ – Yilin Li Mar 25 at 6:35
  • 1
    $\begingroup$ @YilinLi Look at the blue edges, there is a unique path between every two vertices, so what kind of graph is the blue graph and how many blue edges are there? Similarly for the red edges. $\endgroup$ – Michael Biro Mar 25 at 12:08

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.