• Of course, there's no obvious definition of that.
• But one thing we probably do want if possible: no edges crossing.
• For example, the drawing on the right is probably “better”

From Wikipedia Testpad.JPG.

• From the text: connecting utilities (electricity, water, natural gas) to houses. If we can keep from crossing those lines, it will be safer and easier to install.
• Connecting components on a circuit board: the connections on a circuit board cannot cross. If we can connect them without resorting to another layer of traces, it will be cheaper to produce.
• Subway system: if subway lines need to cross, we've got some serious engineering to do.

• Like being bipartite or isomorphic, we can't just draw the graph one way and decide it's not planar.
• There might be another way to draw it so it is planar.

• For example, this graph divides the plane into four regions: three inside and the exterior.

• While we're counting, on this graph $|V|=6$ and $|E|=8$.

• …or any representation of a particular planar graph.

Theorem: [Euler's Formula] For a connected planar simple graph $G=(V,E)$ with $e=|E|$ and $v=|V|$, if we let $r$ be the number of regions that are created when drawing a planar representation of the graph, then $r=e-v+2$.

Proof idea: We proceed by induction on the number of edges. For $e=1$, we can only have this graph, which has $v=2$ and $r=1$, so the theorem holds.

If we assume the conclusion for $e-1$ edges, and add an edge to get our planar graph, there are only two possibilities to consider.

Case 1: we add a pendant vertex and edge. In this case $e$ and $v$ both increase by one and the equality still holds.

Case 2: we add an edge across two existing vertices (that doesn't cross any other edges, of course). Here, $r$ and $e$ both increase by one, preserving the equality.

So we can build any planar graph with $e$ edges and it will always have $r=e-v+2$.

• $Q_3$ has $r=6$, $e=12$, and $v=8$.
• $C_n$ has $r=2$, $e=n$, and $v=n$.

• … but that's all we know so far.
• It would be nice to have a way to decide for sure whether or not a graph is planar, without worrying that we haven't been clever enough in our drawing.

• We don't have any theorems for that (yet), but any way you try to draw them, you'll eventually be unable to draw some of the edges without crossing.
• In some way, these are the “smallest” non-planar graphs.
• We'll see what “smallest” means soon.

Theorem: For a simple connected planar graph with $v\ge 3$ vertices and $e$ edges, $e\le 3v-6$.

Proof: Let $r$ be the number of regions in a planar representation of the graph, and for a region $R$, let $\operatorname{deg}(R)$ be the number of edges that are adjacent to the region, so each edge is adjacent to two regions.

We know that $\operatorname{deg}(R)\ge 3$ for each region since the graph doesn't have multiple edges (for interior regions) and has at least three vertices (for the exterior region). Since each edge is adjacent to two regions,

We can use this with Euler's formula ($r=e-v+2$) to get

• It does show that $K_5$ is non-planar: $v=5$, $e=10$.
• But for $K_{3,3}$, we have $v=6$ and $e=9$. It satisfies the inequality, but is non-planar.

Corallary: A simple connected planar graph with $v\ge 3$ has a vertex of degree five or less.

Proof: Suppose every vertex has degree 6 or more. Then the total number of edges is $2e\ge 6v$. But, because the graph is planar,

Theorem: For a simple connected planar graph with $v\ge 3$ vertices and $e$ edges, and no circuits of length three, $e\le 2v-4$.

Proof idea: Since we have no loops of length three, we can repeat the above proof with $\operatorname{deg}(R)\ge 4$.

• There are still graphs that obey this inequality, but are non-planar.
• Here's one with $v=15$ and $e=18$:

• … and I know it's not planar because of the next theorem.

• … but not simply as subgraphs: the above example doesn't have either as a subgraph.

• One graph is homeomorphic to another if you can turn one into another by adding or removing degree-two vertices:

Theorem: [Kuratowski's Theorem] A graph is non-planar if and only if it contains a subgraph homeomorphic to $K_{3,3}$ or $K_5$.

1. Removing edges and vertices. (Making a subgraph.)
2. Collapsing degree-two vertices into a single edge.
3. Applying an isomorphism to turn it into $K_{3,3}$ or $K_5$.