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

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

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. Apr 22 at 3:07

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.

• The cycle graph $C_{10}$ has 10 vertices and 10 edges, so no need to add any extra edges. Apr 22 at 3:19
• Yep, my bad, will edit. Apr 22 at 3:19
• 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?
– Glo
Apr 22 at 3:47
• 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. Apr 22 at 4:17
• 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. Apr 22 at 13:02