As mentioned in lesson 1, pictorial representations of graphs are really useful representations, but are sometimes inconvenient to use when proving theorems about combinatorial graphs. For example, planar graphs (graphs that can be drawn on a page so that no edges cross) obey the following formula:

where v represents the number of vertices of the graph, e is the number of edges that the graph has, and f is the number of faces that the graph has. (We haven't defined faces yet - they are any portion of the page that is enclosed by edges of the graph).

where k = 1 for a sphere, k = 0 for a Euclidean plane, and k = 1 for a hyperbolic plane. We did the case of the sphere in class. Remember that we put a 'grid' of triangles on the sphere, and then counted up the number of faces, edges and vertices. The formula we got for the sphere was:

which is exactly the same as the formula for the planar graph (i.e. graph that you can draw in the Euclidean plane, a.k.a. a piece of paper). Why is the formula for a planar graph the same as the geometry formula for the sphere (and not the same as the geometry formula for the Euclidean plane) ?

Picture of Graphs Versus Abstract Definitions

One of the approaches that you might have tried in the thinking opportunity above is to draw some examples of planar graphs, and count the numbers of edges, vertices and faces to check to make sure that the formula is correct. Here are some examples:

The vertices have been colored yellow; there are 4 of them. v = 4.

The edges have been colored blue; there are 6 of them. e = 6.

The faces have each been colored a different shade of pink; there are 4 of them. f = 4.

So:

The vertices have been colored yellow; there are 8 of them. v = 8.

The edges have been colored blue; there are 12 of them. e = 12.

The faces have each been colored a different shade of pink; there are 6 of them. f = 6.

So:

The vertices have been colored yellow; there are 20 of them. v = 20.

The edges have been colored green; there are 30 of them. e = 30.

The faces have been colored pink and blue; there are 12 of them. f = 12.

So: v - e + f = 20 - 30 + 12 = 2.

These examples verify the formula, and the pictorial representations of the graphs make it very easy to identify and count the numbers of edges, vertices and faces for each graph. However, if we were to try and prove the formula:

using only these pictorial representations of the graphs, then we would have to draw out every single planar graph, and verify the formula for each picture that we drew. Since there are a lot of possible planar graphs, this would be an impractical approach. One answer to this is to make abstract definitions. These definitions are useful because they let us prove things more easily, but they are usually harder to understand than the pictorial representations of graphs.

Abstract Definitions

The following definitions are from lesson 1:

Definition A graph G consists of a set of vertices and a set of edges, where each edge joins an unordered pair of vertices. The set of vertices of G is denoted by V(G) and the set of edges is denoted by E(G).

Definition A loop is an edge that joins a vertex to itself. A multiple edge occurs when there is more than one edge joining a pair of vertices.

Definition A simple graph is a pair (V(G), E(G)) where V(G) is a non-empty finite set of elements, and E(G) is a finite set of unordered pairs of distinct elements of V(G).

New for this lesson:

Definition Two vertices are said to be adjacent if there is an edge joining them. The vertices are said to be incident to the edge. Similarly, two distinct edges are adjacent if they have at least one vertex in common.

The edges of the following graph are labeled with letters, and the vertices with numbers.

Using Matrices to Represent Graphs

The ideas of adjacency and incidence can be used to come up with different ways of representing a graph.

Let's take a pretty abstract description of a graph G:

One way to represent this information is to point out when a particular edge meets a particular vertex (i.e. when a particular vertex is incident to a particular edge).

For example with the graph:

This information could be represented by drawing a grid like:

The table is filled in by writing '1' in a box if that vertex is incident with that edge, and writing '0' in a box if that vertex is not incident with that edge. The completed table would look like:

Getting rid of the vertex and side labels, the table becomes a matrix known as the incidence matrix:

Incidence Matrix =

More abstractly:

Definition Suppose G is a graph with a vertex set V(G) = {v₁ , , v_n} and an edge set E(G) = {e₁ , , e_n}. We will write v_i ~ e_j if and only if the i^th vertex of G is incident with the j^th edge of G. Then the nm matrix B = [ b_ij ] whose ij^th entry, b_ij, is defined by:

is called the incidence matrix of the graph G.

The idea of adjacency can also be used to describe a graph using a matrix. Again, let's take a pretty abstract description of a graph G:

This information could be represented by pointing out when a particular vertices are joined by edges (i.e. pointing out when vertices are adjacent). Recycling the previous example:

In a similar spirit to the table made to record the incidence information, we could make a table to record the adjacency information:

Adjacency Matrix =

Is it possible for two different graphs to have the same adjacency matrix? Conversely, if two graphs have the same adjacency matrix, are they guaranteed to be the same graph? You might like to try making up some examples to test your hypotheses.

More Definitions

Definition The degree or valency of a vertex of G is the number of edges incident with that vertex.

For example, the degrees of the vertices of the following graph are:

Definition If all the vertices of a simple graph have the same degree, and if k is that common degree then the graph is said to be k regular (alternatively, regular of degree k).

Definition Suppose G is a graph. A subgraph of G is a graph whose vertices all belong to V(G) and whose edges all belong to E(G).

For example, if we a graph resembling:

then some of the subgraphs of this graph (each is drawn using a different color) include:

When are Two Graphs the Same?

Finally in this lesson, let us address the question of what it means for two graphs to be the same. As you can imagine, there are many different ways of drawing the same graph. For example, both of the following are the cube graph:

but they don't look all that similar. The question of when graphs are the same has been implicit in some of the thinking opportunities. For example, to decide whether the incident and adjacency matrices are different for different graphs, you have to decide what it means for graphs to be different in the first place, and this can sometimes be very hard to tell from the pictures. For example, believe it or not, the following graph:

is the cube graph too. In graph theory, two graphs which are really the same are called isomorphic. This means that one pictorial representation of one graph can be re-drawn (preserving all of the vertices and edges) to resemble the other graph. If you attended the summer course Geometry and the Imagination, you might remember "schmooshing" operations. Two graphs are isomorphic if you can schmoosh one into the other. As an example, let's schmoosh this funny looking graph into the cube graph (colors are added to show how the schmooshing goes).

In abstract terms, isomorphism is defined:

Definition Two graphs, G₁ and G₂, are isomorphic if there is a one-to-one correspondence between the vertices of G₁ and those of G₂ with the property that the number of edges joining any two vertices of G₁ is equal to the number of edges joining the corresponding vertices of G₂.

Definition If G is a graph with vertex set V(G) = { v₁ , , v_n } then the nn matrix

A = [ a_ij ] whose ij^th entry is the number of edges joining vertex I to vertex j is called the adjacency matrix.