Can a connected planar graph have 10 vertices and edges? is this possible?

Question

Using Euler’s formula, $V − E + F = 2$.

$10 − 10 + F = 2$,
Therefore $F = 2$.

Do I also need to use this formula: $2E$ $\geq$ $3F$? or Do I use $E \leq 3v-6$?

I'm a little lost if this type of graph is possible or not and how to go from here. Thanks!

If you plug the $10$s you are given into the last two inequalities, they are satisfied. There is a general class of graphs with the same number of edges and vertices. — Ross Millikan, Commented Apr 22 at 3:07

Red Five · Accepted Answer · 2024-04-22 03:20:27Z

6

Yes.

Draw a cycle graph $C_{10}$ (10 vertices, 10 edges) and you're done.

This is only one solution, there are lots of others.

Another idea would be to create a simple walk over 10 vertices (9 edges) then connect any two vertices.

edited Apr 22 at 3:20

answered Apr 22 at 3:11

Red Five

2,7924 gold badges11 silver badges27 bronze badges

2

$\begingroup$ The cycle graph $C_{10}$ has 10 vertices and 10 edges, so no need to add any extra edges. $\endgroup$
– Gordon Royle
Commented Apr 22 at 3:19
$\begingroup$ Yep, my bad, will edit. $\endgroup$
– Red Five
Commented Apr 22 at 3:19
$\begingroup$ I now understand the 𝐶10 graph! Thank you! I am still a little confused on "a simple walk over 10 vertices (9 edges) then connect any two vertices.". Why is 9 edges allowed in this case? $\endgroup$
– Glo
Commented Apr 22 at 3:47
$\begingroup$ If you have a straight walk through $n$ vertices, you need $n-1$ edges. You can connect any two non-adjacent (or adjacent I guess, it doesn't really matter) vertices to add the $n^{th}$ edge and remain planar. $\endgroup$
– Red Five
Commented Apr 22 at 4:17
$\begingroup$ If you only want to consider connected graphs, than you can get all possible 10 edges, 10 vertices graphs by drawing any tree graph on 10 vertices (which as a tree will automatically have 9 edges) and then connect any two of the vertices for a planar graph with 10 edges and 10 vertices. $\endgroup$
– quarague
Commented Apr 22 at 13:02

Add a comment |

1 Answer 1