Consider a planar graph with 2n vertices which has two faces that are n-gons, and all remaining faces are triangles. How many edges does this graph have?

  • $\begingroup$ Welcome to MSE. It will be more likely that you will get an answer if you show us that you made an effort. $\endgroup$ – José Carlos Santos May 15 '18 at 16:14
  • 1
    $\begingroup$ What have you tried? You might draw some graphs for small $n$ and count them. You might use the Euler characteristic $V+F-E=2$ $\endgroup$ – Ross Millikan May 15 '18 at 16:16
  • $\begingroup$ @JoséCarlosSantos Thank you! I was trying to express faces as f = 2n + 3x , where 2- number of n- gons , n - number of vertices n-gon have , 3 - number of vertices triangle have, and x - number of triangles, but I feel like it's a wrong path to go. Also, we all know about double counting and planar graph, means 2*#e = deg*#v, but I'm not sure if it's applicable here. As well,I tried to express #e using faces: #e = p/2 *#f, where p - number of corners of each face. That is all I have for now( $\endgroup$ – J.Doe May 15 '18 at 16:26
  • $\begingroup$ I think you mean $E=2n+3x$, and that's almost right, but each edge will appear in two faces, so that expression counts each edge twice. Furthermore, how can you express $x$ in terms of $F$? $\endgroup$ – Kevin Long May 15 '18 at 17:41
  • $\begingroup$ No, I meant F = 2n + 3x, meaning that number of faces consist of 2 n-gons and unknown number of triangles, which is x. And using the formula #e = p/2 *#f, where p - number of corners of each face, we can get E = E1 + E2 = n^2 + 9x/2. But I don't know how to get rid of x? $\endgroup$ – J.Doe May 15 '18 at 18:04

Draw two concentric $n-$gons with the inner one clocked slightly so that its vertices are between the vertices of the outer one. You have accounted for all $2n$ vertices, so you can't have any more. Now draw the band of obvious triangles between the $n-$gons. Each triangle has a base on one of the $n-$gons and two sides that it shares with other triangles, so there are $2n$ triangles. There are $n$ edges in each $n-$gon and one between each pair of neighboring triangles, for $4n$ in total. A version of the figure with $n=8$ is below.
enter image description here

If the question setter has been fair, s/he has promised you that the number of edges is the same for all configurations that meet the requirement, so you are done.

  • $\begingroup$ Thank you so much! But is there a way to explain it using formulas? $\endgroup$ – J.Doe May 15 '18 at 22:46
  • $\begingroup$ Yes, we have $V=2n, F=2n+2,$ so $E=4n$ from the Euler Characteristic that I mentioned in my first comment. $\endgroup$ – Ross Millikan May 15 '18 at 22:56
  • $\begingroup$ how do we know that F=2n+2 without drawing the graph? $\endgroup$ – J.Doe May 15 '18 at 23:15
  • $\begingroup$ You start with the two $n-$gons, so have $2n$ edges and the region between the $n-$gons needs to be cut into triangles. Each new side needs to go between two existing vertices. You can compute the number of triangles by the total angle. The interior $n-$gon contributes $2\pi n-\pi(n-2)$ in exterior angles and the exterior $n-$gon contributes $pi(n-2)$ in interior angles. That totals $2\pi n$ so it takes $2n$ triangles $\endgroup$ – Ross Millikan May 15 '18 at 23:27

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.