Verify that the Euler's formula is correct?

2 Answers
Jun 25, 2018

Answer:

(see below)

Explanation:

I have taken that you really did mean "verify" which implies that there should have been a sample to verify. It is also possible that you really meant "prove"; if so re-submit this question with proper terminology.

I have also assumed that, since this was asked under the Geometry topic, you meant Euler's Formula relating Vertices, Edges, and Faces for planar figures in Euclidean space (Euler has several formulae in different areas).

Here is a sample for verification:
enter image source here
As we can see this figure (or "graph") has:
#7# Vertices;
#9# Edges; and
#4# Faces.

Euler's Formula says
#color(white)("XXX")V-E+F=2#
and for the sample (above) since
#color(white)("XXX")7-9+4=2#
we have verified Euler's Formula (for this example).

Jun 26, 2018

Answer:

Proof by induction below:
(it is long, but not very complicated)

Explanation:

Before we can prove Euler's Formula for Planar Graphs it is necessary to clarify the environment. For the purpose of this discussion, a Planar Graph:

Is composed of three types of elements:

  • Vertices: points in Euclidean space which are terminal points of edges. Note that a vertex can not exist without at least one edge attached to it.
  • Edges: lines in Euclidean space each with two terminal points (which are either the same or two different vertices) and which do not intersect (touch) other edges.
  • Faces: areas of Euclidean space bounded by edges or external to any bounded space.

Furthermore

  • a Planar Graph must be connected; that is for any two vertices of the planar graph there must be a path composed of edges (and connecting vertices) joining the two vertices.
  • a Planar Graph can not be null; it must contain at least one vertex.

Common Variables:
#V#: the number of vertices in a planar graph.
#E#: the number of edges in a planar graph.
#F#: the number of faces in a planar graph.

Euler's Formula for Planar Graphs:
#color(white)("XXX")V-E+F=2#

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Based on the above:

A minimal planar graph will contain 1 vertex, 1 edge (with both ends connected to the vertex), and 2 faces: one inside the loop created by the edge looping back to the vertex and one outside that loop.

Let us suppose that Euler's Formula is true for
#color(white)("XXX")V <= n_v#, and
#color(white)("XXX")E <= n_e#, and
#color(white)("XXX")F <= n_f#

Option 1: Adding a Vertex
Consider generation of a planar graph with #n_v+1# vertices from some planar graph that satisfies Euler's Formula.

We know that prior to adding the #(n_v+1)^("st")# vertex, the prior graph must satisfy Euler's formula.

There are two possibilities:
- The new vertex is not on an existing edge. In this case a new edge must also be added (see discussion of composition above). That is if we add such a vertex, #V# will increase by #1# but so must #E# and Euler's Formula continues to be valid.
- The new vertex is on an existing edge. In this case #V# is increased by #1# but an existing edge is split into two edges, so that #E# also increases by #1# (and Euler's Formula remains valid).

Option 2: Adding an Edge Without Adding a Vertex
Again there are two possibilities:
- Both end of the new edge are connected to the same vertex. In this case we have a loop which encloses a new face within an existing face. Adding a new edge in this way increases #E# by #1# but it also increases #F# by #1# so Euler's Formula remains valid.

  • The new edge connects two different vertices. Since (see earlier comments) there must already have been a path of edges between the two vertices, adding an edge will close off an new face; increasing #E# by #1# will also increase #F# by #1# and Euler's Formula continues to be valid.

Note: there is no Option 3: Adding a Face Without Adding a Vertex or Edge.