2
$\begingroup$

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

Attempt:

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.

$\endgroup$
3
  • $\begingroup$ Euler's formula counts the external face. Your graph has 9. $\endgroup$ Commented Dec 9, 2018 at 2:50
  • $\begingroup$ 3 minutes. $ $ $ $ $\endgroup$
    – Did
    Commented Dec 9, 2018 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
    Commented Dec 9, 2018 at 10:59

2 Answers 2

4
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ @greedoid 5. As is mentioned in my post. $\endgroup$
    – Did
    Commented Dec 9, 2018 at 11:03
  • $\begingroup$ I don't understand. What have I proved then? $\endgroup$
    – nonuser
    Commented Dec 9, 2018 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
    Commented Dec 9, 2018 at 11:15
3
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Commented Dec 9, 2018 at 0:47
  • $\begingroup$ Yes it is, but your graph is clearly connected, it has to many edges to not be connected $\endgroup$
    – nonuser
    Commented Dec 9, 2018 at 0:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .