2
$\begingroup$

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!

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 22 at 3:07

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ The cycle graph $C_{10}$ has 10 vertices and 10 edges, so no need to add any extra edges. $\endgroup$ Apr 22 at 3:19
  • $\begingroup$ Yep, my bad, will edit. $\endgroup$
    – Red Five
    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
    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
    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
    Apr 22 at 13:02

You must log in to answer this question.

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