Let $G$ a simple $2$-connected planar graph so that all vertices are incident with the infinite region. Suppose that every bounded region of $G$ has length $3$ (so is a cycle of length $3$). Let $k$ be the number of vertices of degree $2$ in $G$, and let $r$ be the number of regions of $G$ sharing no edges with the infinite region.

If $|V(G)| > 3$, show that \begin{align} k = r + 2 \end{align} I'm trying to figure out how to go about this. So, I think that these could be of help:

  • $|E|−|V|=|R|−2$
  • Every edge bounds two regions
  • If the region shares no edge with the infinite region, then it only shares edges with other regions of length 3.
  • $\sum\deg(v)=2|E(G)|$
  • $12≤ \sum[6−\deg(v)]$ so $\sum\deg(v)≤6|V(G)|−12$
  • for $2$-connected graphs, every vertex has $\deg(v)≥2$

Any ideas?


The graph you describe corresponds to a triangulation of a convex polygon. Consider the dual tree of your graph as shown in the picture.

enter image description here

The leaves in the tree are in 1-1 correspondence to the degree 2 vertices of the graph, the branching nodes correspond to the faces with no edge on the boundary. So

  • $k=$ degree-1 nodes of the tree,
  • $r=$ degree-3 nodes of the tree.

Contract all the degree one tree nodes. This gives almost a full binary tree, if you select one of the degree-3 nodes as root. "Almost", since the root has 3 children. For such a tree we have by induction #leaves=#interior nodes +2. And hence $k=r+2$.

  • $\begingroup$ thanks for the help! though i can't follow the last paragraph. could you elaborate if you have the time? i'd really appreciate it! $\endgroup$ – DustinH Dec 2 '12 at 21:02

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.