0
$\begingroup$

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?

1 Answers 1

2

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

  • 0
    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!2012-12-02