Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

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

share|improve this answer
    
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! –  DustinH Dec 2 '12 at 21:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.