Ex-plane something to me…

happy

Planar Graphs & Euler’s Theorem

A planar graph is a graph which can be drawn in the plane without any edges crossing. Some pictures of a planar graph might have crossing edges, but it’s possible to redraw the picture to eliminate the crossings.

There are also many practical applications with a graph structure in which crossing edges are a nuisance, including design problems for circuits, subways, utility lines. Two crossing connections normally means that the edges must be run at different heights.

When a planar graph is drawn with no crossing edges, it divides the plane into a set of regions, called faces. By convention, we also count the unbounded area outside the whole graph as one face.

Suppose that we have a graph with e edges, v nodes, and f faces. We know that the Handshaking theorem holds, i.e. the sum of  the degrees of the vertices is 2e. For planar graphs, we also have a Handshaking theorem for faces: the sum of the face degrees is 2e.

For connected planar graphs, we have Euler’s formula: v − e + f = 2. We’ll prove that this formula works.

Before we try to prove Euler’s formula, let’s look at one special type of planar graph: trees.

A tree doesn’t divide the plane into multiple regions, because it doesn’t contain any cycles. In graph theory, a tree has only one face: the entire plane surrounding it. So Euler’s theorem reduces to v − e = 1,
i.e. e = v − 1. Let’s prove that this is true, by induction.

Proof by induction on the number of edges in the graph.

Base Case: If the graph contains no edges and only a single vertex, the formula is clearly true.

IHOP: Suppose the formula works for all trees with up to k vertices. Let T be a tree with k + 1 vertices.
We need to show that T has k edges.
Now, we find a vertex with degree 1 (only one edge going into it). To do this start at any vertex r and follow a path in any direction, without repeating edges. Because T has no cycles, this path can’t return to any vertex it has already visited. So it must eventually hit a dead end: the vertex at the end must have degree 1. Call it p.

Remove p and the edge coming into it, making a new tree T′ with k vertices. By the IHOP, T′ has k − 1 edges. So T has k edges. Therefore the formula holds for T.

Spanning-Tree1

We can now prove Euler’s Formula (v − e + f = 2) works in general, for any connected planar graph.

Proof by induction on the number of edges in the graph.

Base Case: If e = 0, the graph consists of a single node with a single face surrounding it. So we have 1 − 0 + 1 = 2 which is clearly right.

IHOP: Suppose the formula works for all graphs with no more than n edges. Let G be a graph with n + 1 edges.

Case 1: G doesn’t contain a cycle. So G is a tree and we already know the formula works for trees since we proved it! Check!

Case 2:  G contains at least one cycle. Pick an edge p that’s on a cycle. Remove p to create a new graph G′.

Since the cycle separates the plane into two faces, the faces to either side of p must be distinct. When we remove the edge p, we merge these two faces. So G′ has one fewer faces than G.

Since G′ has n edges, the formula works for G′ by the IHOP.

That is, v′ − e′ + f′ = 2.

But v′ = v, e′ = e − 1, and f′ = f − 1.

Substituting, we find that

v − (e − 1) + (f − 1) = 2
So, v − e + f = 2                   as desired.

Euler-Formula-for-Planar-Graph2

 

Exam Time!

Use Euler’s Planar Graph Theorem to prove whether the graph is planar or nonplanar.

planar8

 

 

 

 

http://www.science4all.org/le-nguyen-hoang/eulers-formula-and-the-utilities-problem/

About mathelogicalmayhem

I am pursuing a B.S. in Secondary Education with concentration in Mathematics (of course!). View all posts by mathelogicalmayhem

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: