Verify that the Euler's formula is correct?
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:
As we can see this figure (or "graph") has:
Euler's Formula says
and for the sample (above) since
we have verified Euler's Formula (for this example).
Proof by induction below:
(it is long, but not very complicated)
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.
- 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.
Euler's Formula for Planar Graphs:
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
Option 1: Adding a Vertex
Consider generation of a planar graph with
We know that prior to adding the
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,
- The new vertex is on an existing edge. In this case
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
- 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.