Draw a planar graph with two vertices of degree 3 and four vertices of degree 5, if possible.


With handshaking lemma, I get this:

$2e = 26 \implies e=13$

Then with Euler's formula, I get:

$6-13+f=2 \implies f = 9$

However, since $e \leq 3v - 6$ for a simple, connected, planar graph I would get:

$13 \leq 3(6)-6$

$13 \leq 12$

I can't figure out how I could get 9 faces for my graph. I can only get 8 faces as shown here:

enter image description here

This is the best attempt I had on this problem with no success.

  • $\begingroup$ Euler's formula counts the external face. Your graph has 9. $\endgroup$ – Misha Lavrov Dec 9 '18 at 2:50
  • $\begingroup$ 3 minutes. $ $ $ $ $\endgroup$ – Did Dec 9 '18 at 10:54
  • $\begingroup$ I had no trouble drawing a simple connected planar graph with two vertices of degree $3$ and four vertices of degree $5$. It is a tree of order $22$. (Was there some other condition you didn't mention?) $\endgroup$ – bof Dec 9 '18 at 10:59

Here is a planar example. The vertices A and B are linked by two simple edges. The vertices A, B, E and F have degree 5. The vertices C and D have degree 3.

enter image description here

  • 1
    $\begingroup$ @greedoid 5. As is mentioned in my post. $\endgroup$ – Did Dec 9 '18 at 11:03
  • $\begingroup$ I don't understand. What have I proved then? $\endgroup$ – Maria Mazur Dec 9 '18 at 11:05
  • $\begingroup$ @greedoid That no graph such that, between two given vertices, there are either zero or one edge, solves the question. And I provided a graph solving the question such that, between two given vertices, there are either zero or one or two edges (when one admits more than one edge, these are often called multi-edged graphs). No mathematical mystery here. (But the reason why the OP, who is obviously considering graphs with multi-edges, chose to instantly accept an answer dealing only with graphs without multi-edge, is a true mystery, yes.) $\endgroup$ – Did Dec 9 '18 at 11:15

From formula you wrote $e\leq 3v-6$ you can see that such a (planar) graph does not exist.

Also you could note that this graph contains $K_{3,3}$ so again it can not be planar.

Edit: Actualy this graph doesn't even exist since the sequence $5,5,5,5,3,3$ is not graphicaly. If it is, then following would be also

$$ 4,4,4,2,2\implies 3,3,1,1\implies 2,0,0$$ but last one clearly it is not graphicaly.

  • $\begingroup$ Can you still get a planar graph even if it's not a simple, connected one based on the formula? I thought that formula was just for simple, connected planar graphs. $\endgroup$ – cosmicbrownie Dec 9 '18 at 0:47
  • $\begingroup$ Yes it is, but your graph is clearly connected, it has to many edges to not be connected $\endgroup$ – Maria Mazur Dec 9 '18 at 0:48

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.