Planar Graph Practice Questions

For any planar graph, Euler's formula states that $V - E + F = 2$, where $V$ is the number of vertices, $E$ is the number of edges, and $F$ is the number of faces. Given $V=n$, we have $n - E + F = 2$.
The sum of degrees of all vertices in a graph is $2E$. If the minimum degree $\delta \geq 3$, then $2E = \sum \deg(v) \geq n\delta$.
Since $\delta \geq 3$, we have $2E \geq 3n$, which implies $E \geq \frac{3n}{2}$.
Substituting this into Euler's formula: $n - \frac{3n}{2} + F \geq 2$.
Rearranging the inequality for $F$: $F \geq 2 - n + \frac{3n}{2}$, which simplifies to $F \geq \frac{n}{2} + 2$.

For any connected planar graph, Euler's formula relates the number of vertices ($V$), edges ($E$), and faces ($F$) in any planar embedding:
$V - E + F = 2$
Given $V=10$ vertices and $E=15$ edges, we can find the total number of faces $F$:
$10 - 15 + F = 2$
$-5 + F = 2$
$F = 7$
In any planar embedding, exactly one face is unbounded. The number of bounded faces is the total number of faces minus the one unbounded face.
$F_{\text{bounded}} = F - 1 = 7 - 1 = 6$

A planar graph is a graph that can be drawn on a plane without any edges crossing.
K4 (the complete graph with 4 vertices) can be redrawn to avoid edge crossings, demonstrating it is planar.
Q3 (the cube graph with 8 vertices) is also known to be a planar graph, as it can be drawn on a plane without edge intersections.
Since both K4 and Q3 can be drawn without edge crossings, both are planar graphs.

According to Kuratowski's Theorem, a graph is non-planar if and only if it contains a subdivision of $K_5$ or $K_{3,3}$ as a subgraph.
To find the non-planar graph with the minimum number of edges, we compare the number of edges in $K_5$ and $K_{3,3}$.
$K_5$ is the complete graph on 5 vertices. It has $v=5$ vertices and $e = \binom{5}{2} = 10$ edges.
$K_{3,3}$ is the complete bipartite graph with 3 vertices in each partition. It has $v=3+3=6$ vertices and $e = 3 \times 3 = 9$ edges.
The minimum number of edges among these fundamental non-planar graphs is 9, corresponding to $K_{3,3}$. $K_{3,3}$ has 6 vertices and 9 edges.

The final answer is $\boxed{B}$