Let $G$ be a plane graph of order $n$ and size $m$ for which the boundary of every interior region of $G$ is a triangle, and the boundary of the exterior region is a $k$-cycle, ($k>2$). What is $m$ in terms of $n$ and $k$?
Use Euler's identity to get things started, $n-m+r=2$, $\; r$ is the number of regions. So we can find how many triangles there will be in the graph. I'm a little stuck because I don't know how I can use $k$ here. If I could somehow find the number of bridges I might be getting somewhere, but $k$ doesn't tell us that. The graph could be a tree or even a single path. I've done a few random graphs and I can't see a pattern between $m$ and $n$ & $k$. If someone could give me a jump start I would really appreciate it.
Hint: Add up the number of edges bounding each region (in terms of $r$ and $k$), and note that this will be equal to $2m$. Then use Euler's formula to get $r$ in terms of $m$ and $n$.