2
$\begingroup$

Problem:

Let $G$ be a planar graph with girth (= length of the shortest cycle in that graph), such that each face, including the outer one is bounded by a cycle. ($G$ does not contain any vertices of degrees $0$ or $1$, and it contains at least one cycle.)

a) Prove that if the girth of $G$ is at least $6$, $G$ contains vertex of degree $2$
b) Prove that if the girth of $G$ is at least $11$, $G$ contains two adjacent vertices of degree $2$.
c) Find a graph with girth of $10$ (or as large as possible) that does not contain two adjacent vertices of degree $2$.

My thoughts:

a) is True
Let's assume that there is no vertex of degree $2$, then all vertices must have $\deg(v) \ge 3$.
$$\sum_{v\in V} \deg(v) = 2|E|$$ from which we can get that $3|V| \le 2|E|$ which contradicts with Euler's formula $2|E|\le3|V|-6$.

b) I'm not really sure how to solve that, given the two adjacent vertices.
c) I think it should be similar to how b) is solved.

Are my thoughts on a) correct?
How should I approach problem b) and c)?

$\endgroup$
1
  • $\begingroup$ You did not use the condition that the girth of $G$ is at least $6$ in any way. Without this condition, your statement is not true. For example, the graph $K_4$ is planar, but all its vertices have degree $3$. $\endgroup$
    – kabenyuk
    Commented Jan 8, 2023 at 14:13

1 Answer 1

2
$\begingroup$

For question (a) you can reason like this. We can assume that the graph $G$ is connected (otherwise take the connected component instead of $G$). So let $G$ be a connected planar graph with $v$ vertices and $e$ edges and $f$ faces. We know that

\begin{align} \tag1 &\sum_{x\in V(G)}\deg(x)=2e, \\ \tag2 &\sum_{F\in F(G)}d(F)=2e,\\ \tag3 &v-e+f=2. \end{align}

Here $F(G)$ is the set of faces of graph $G$, $d(F)$ is the size of face $F$. If the degree of each vertex is at least $3$ and the size of each face is at least $6$, then from (1)-(3) we obtain $$ 2e=\sum_{x\in V(G)}\deg(x)\geq3v, $$ and $$ 2e=\sum_{F\in F(G)}d(F)\geq6f, $$ and $$ 2=v-e+f\leq\frac{2}{3}e-e+\frac{1}{3}e=0. $$ Contradiction.

Question (b). Suppose the graph $G$ has no adjacent vertices of degree $2$. Consider an arbitrary face $F\in F(G)$. Since this face has no adjacent vertices of degree $2$, at most half of all vertices of $F$ have degree $2$. Since $d(F)\geq11$, we have that at least $6$ of vertices of face $F$ have degree $\geq3$.

Now pay attention to the most important thing. Let us do smoothing of each vertex of degree 2. (This means the following. Let $\deg(x)=2$ and let $u$ and $v$ be neighbors of $x$. We remove vertex $x$ along with edges $xu$, $xv$ and add edge $uv$.) As a result, we obtain a connected planar graph $G'$ each vertex of which has degree at least $3$ and each face of which has size at least $6$. The latter is impossible, we proved this in (a).

Question (с). Let us construct an example based on the considerations of the previous problem. Take a dodecahedron graph. All faces of this graph have size $5$ and all vertices of degree $3$. Add one vertex to each edge of this graph (this operation is called subdivision of an edge). We obtain a planar graph in which each face has size $10$ and no adjacent vertices of degree $2$.

$\endgroup$

You must log in to answer this question.

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