# Planar graph with girth of certain length

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)?

• 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$. Commented Jan 8, 2023 at 14:13

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$$.