1
$\begingroup$

Lemma: Suppose that a plane simple graph on $n ≥ 4$ vertices with the minimal degree of a vertex at least $3$ does not have faces of degree $4$ or $5$. Prove that there are at least $4$ faces of degree $3$ (triangles) in this graph.

I saw that a similar question was asked by Dolva Planar graph, number of faces, minimum vertex degree 3. Where the Handshaking lemma and Euler's formula $v-e+f=2$ were suggested. But I am still stuck.

Any advice or help is welcome. Thanks in Advance!

$\endgroup$
5
  • $\begingroup$ @kabenyuk I actually drew a graph using n=4 satisfying the given condition but it is not containing 4 faces of degree 3. $\endgroup$
    – Logo
    May 3, 2021 at 17:36
  • $\begingroup$ @Kabenyuk could please explain in details how you got proved it $\endgroup$
    – Logo
    May 3, 2021 at 17:36
  • $\begingroup$ @Violet It would be interesting to look at your drawing. Note that this is not a proof, just hints. $\endgroup$
    – kabenyuk
    May 4, 2021 at 9:48
  • $\begingroup$ @kabenyuk yeah I understood what I did wrong....I forgot to consider the outer region face and how to calculate it's degree.... $\endgroup$
    – Logo
    May 4, 2021 at 12:19
  • 1
    $\begingroup$ That's what I thought. $\endgroup$
    – kabenyuk
    May 6, 2021 at 6:54

1 Answer 1

1
$\begingroup$

Hints:

  1. $v\leq2e/3$;
  2. $3k+6(f-k)\leq2e$, $k\leq3$, then $f\leq e/3+k/2$;
  3. $2=v-e+f\leq 2e/3-e+e/3+k/2=k/2\leq3/2$.
$\endgroup$
4
  • $\begingroup$ I did not understand how did you get the second one $\endgroup$
    – Logo
    May 3, 2021 at 17:05
  • $\begingroup$ Hello @kabenyuk please could you still explain the propositions (1) and (2). And what step do I need to take further. I have been trying to solve it but still stuck. thanks $\endgroup$
    – Pacific
    May 3, 2021 at 18:04
  • $\begingroup$ Let $V$ be the vertex set of our graph. Since $\sum_{u\in V}{\rm deg}(u)=2e$ and $ {\rm deg}(u)\geq3$ for each vertex $u$ of $V$, it follows that $v\leq2e/3$. Let $\cal F$ denote the set of all faces and $k$ denotes the number of faces of degree 3. Since $\sum_{F\in\cal F}d(F)=2e$ and $d(F)\geq6$ or $d(F)=3$, it follows that $f\leq e/3+k/2$. $\endgroup$
    – kabenyuk
    May 4, 2021 at 3:59
  • $\begingroup$ Thanks @kabenyuk it was helpful $\endgroup$
    – Pacific
    May 4, 2021 at 10:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .