Welcome to a lesson on planar graphs.
When a connected graph can be drawn
without any edges crossing, it is called planar.
When a planar graph is drawn in this way,
it divides a plane into regions called faces.
So again, a planar graph is a connected graph
that can be drawn without any edges crossing.
Even if a graph does not look like it is planar,
it still might be.
Perhaps we can redraw it in a way in which no edges cross.
For example, the graph below is planar
because it can be redrawn as the graph on the right.
The two graphs are the same.
So if one is planar, the other must be too.
However, the original drawing of the graph was
not a planar representation of the graph.
And again, when a planar graph is drawn
without edges crossing, the edges and vertices
of the graph divide the plane into regions,
and we call each region a face.
The graph above has three faces.
Yes, we do include the outside region as a face.
So again, we have two inner regions
and one outside region giving us a total
of three regions or three faces.
The number of faces does not change
no matter how we draw the graph
as long as we do so without the edges crossing.
So it makes sense to ascribe the number of faces
as a property of the planar graph.
One word of caution, we can only count faces
when the graph is drawn in a planar way.
For example, consider the two representations
of the same graph below.
If we count faces using the graph on the left,
we might say there are five faces including the outside,
again, four inner faces
and one outside face giving a total of five faces.
But drawing the graph with a planar representation shows
that, in fact, there are only four faces,
three inner faces and one outer face giving us
a total of four faces.
So before we determine the number of faces,
we must always have a planar representation.
And there is a connection
between the number of vertices, v,
the number of edges, e,
and the number of faces, f, in all connected planar graphs.
This relationship is called Euler's Formula.
Euler's Formula states for any connected planar graph
with v vertices, e edges, and f faces,
we have v minus e plus f equals two.
Again, this is for all connected planar graphs.
Why is Euler's Formula true?
One way to convince ourselves of its validity is
to draw a planar graph step by step
starting with the graph of P two shown here below
where we have two vertices connected by one edge.
Any connected graph, besides just a single isolated
vertex must contain this sub graph.
Now build up the graph by adding edges and vertices.
Each step will consist
of either adding a new vertex connected by a new edge
to part of the graph, which we'll call a spike,
or by connecting two vertices
already in the graph with a new edge.
So again, when building the graph,
each step we will either add a spike,
which is an edge and a vertex shown here on the left,
or just one edge shown here on the right
by connecting two existing vertices.
And what do these moves do?
When adding a spike,
meaning an edge and a vertex, shown here on the left,
the number of edges increases by one.
The number of vertices increases by one,
and the number of faces remains the same.
But this means that v minus e plus f does not change
because v and e increase by one and one minus one is zero.
Completing a circuit by adding an edge connecting
two existing vertices adds one edge, adds one face,
and keeps the number of vertices the same.
Well, if we increase the number of edges by one
and increase the number of faces by one,
since negative one plus one is zero,
v minus e plus f does not change.
So we can build any graph using a combination
of these two moves, and doing so
never changes the quantity v minus e plus f.
That quantity will be the same for all graphs.
Notice for our starting graph, P two,
the number of vertices is two,
the number of edges is one,
and the number of faces is one
which gives us v minus e plus f equals two
because we have two minus one plus one
which does equal two.
This argument is essentially a proof by induction.
Now, not all graphs are planar.
If there are too many edges and too few vertices,
then some of the edges will need to intersect.
The smallest graph where this happens is
K five, pictured here below.
We'll talk more about non-planar graphs in the next lesson.
I hope you found this helpful.