Consider a planar graph with 5 vertices, what is the minimum and the maximum number of edges such a graph can have?
The graph need not be connected and is simple.
[Math] Planar Graph max min edges
discrete mathematicsgraph theoryplanar-graphs
discrete mathematicsgraph theoryplanar-graphs
Consider a planar graph with 5 vertices, what is the minimum and the maximum number of edges such a graph can have?
The graph need not be connected and is simple.
Best Answer
$K_5$ contains $10$ edges and it is not planar (as $e\le 3v-6$ fails). A graph of $5$ vertices with $9$ edges would do as it won't contain a sub-division of $K_5$ or $K_{3,3}$. (See Kuratowski's theorem)