Euler's Formula

Euler's Formula is a fundamental theorem in graph theory, named after the Swiss mathematician Leonhard Euler. It relates the number of vertices (V), edges (E), and faces (F) of a connected planar graph in two dimensions. The formula can be expressed as:

Euler's Formula holds true for many planar graphs, and it provides deep insights into the relationships between these graph components.

Example 1

Suppose we have a planar graph with 6 vertices and 9 edges. How many faces does this graph have?

Using Euler's Formula:

So, the given planar graph has 5 faces.

Subgraphs

A subgraph is a graph formed by selecting a subset of vertices and a subset of edges from G while preserving the same vertex set and ensuring that the selected edges have both of their endpoints within the selected vertices. Subgraphs allow us to focus on specific portions of a larger graph.

Example 2

Notice how the three graphs in blue are a selection of vertices and edges from the graph in red.

Trees

A tree is a special type of graph that is acyclic (contains no cycles) and connected (there is a path between any pair of vertices). Trees have several important properties, such as having exactly one fewer edge than vertices. They are widely used in computer science, data structures, and algorithms. In example 2 the 1st and 3rd graphs (from the left) are trees.

Bipartite Graphs

A bipartite graph is a graph whose vertex set can be divided into two disjoint sets (parts) such that no edges exist between vertices within the same set. In other words, all edges connect vertices from one set to the other. Bipartite graphs have many practical applications, including modelling relationships between two distinct sets of objects.

Example 3

The below bipartite graph illustrates the output of a function, f(x).