Start by watching this video:

📹 Definition of a Graph

The Königsberg bridge problem can be represented diagramatically by means of a set of points and lines. The points $P$, $Q$, $R$ and $S$ are called vertices, the lines are called edges and the whole diagram is called a graph.

2.1. Vertices and Edges

A graph, $G$, is a mathematical structure which consists of:

(i). a vertex set $V = V(G)$ whose elements are called vertices of $G$.

(ii). an edge set $E = E(G)$ of unordered pairs of distinct vertices called edges of $G$. Note that $E$ is actually a multiset in that some unordered pairs can be repeated to represent more than one edge joining two vertices.

(iii). a relation that associates with each edge two vertices, which are not necessarily distinct, called its endpoints.

Such a graph is denoted $G = \{V(G), E(G)\}$ , if we want to be specific about which graph $G$ we are referring to, or just simply $G = \{V, E\}$ .

Example 1

An undirected graph is a graph in which the edges have no orientation. Hence, in an undirected graph the edge set is composed of unordered vertex pairs. In 📷 Figure 3 for example, the edge $\{1, 2\}$ is considered identical to the edge $\{2, 1\}$ .

An edge-endpoint function on a graph $G$ defines a correspondence between edges and their endpoints.

Example 2

If $X$ and $Y$ are vertices of a graph, $G$, then $X$ and $Y$ are said to be adjacent if they are joined by an edge.

An edge in a graph that joins two vertices is said to be incident to both vertices.

Example 3

Two edges connecting the same vertices are called multiple or parallel edges. In Figure 4 edges $f$ and $g$ are parallel edges.

Graphs like the one shown here, containing parallel edges, are called multigraphs and we shall look at these in more detail later in the unit.

The order of a graph $G$, denoted $\mid V(G)\mid$, is the number of vertices contained in $G$.

In 📷 Figure 3, $\mid V(G) \mid = 4$.

The size of a graph $G$, denoted $\mid E(G)\mid $, is the number of edges contained in $G$.

In 📷 Figure 3, $\mid E(G)\mid = 5$.

The degree of a vertex $X$, written $deg(X)$, is the number of edges in $G$ that are incident with $X$.

In 📷 Figure 3, $deg(1) = 2$, $deg(2) = 3$, $deg(3) = 2$ and $deg(4) = 3$.

Any vertex of degree zero is called an isolated vertex and a vertex of degree one is an end-vertex.

Example 4

A vertex is said to be even or odd according to whether its degree is an even or odd number. In 📷 Figure 3 vertices $2$ and $4$ are odd while vertices $1$ and $3$ are even.

If the degrees of all the vertices in a graph, $G$, are summed then the result is an even number. Furthermore, this degree is twice the number of edges, as each edge contributes $2$ to the total sum. We have the following lemma:

The Handshaking Lemma

In any undirected graph the sum of the vertex degrees is equal to twice the number of edges, i.e.

$$\sum_{X \in V[G]} deg(X) = 2 \mid E(G) \mid .$$

Proof: In a graph $G$ an arbitrary edge $\{X, Y\}$ contributes $1$ to $deg(X)$ and $1$ to $deg(Y)$. Hence the degree sum for the graph is even.

Note: A corollary of the Handshaking Lemma states that the number of odd vertices in a graph must be even. So, for example, we cannot have a graph with $5$ even vertices and $5$ odd vertices as the degree sum would be an odd number, contradicting the Handshaking Lemma.

Watch the Handshaking Lemma video at:

📹 Sum of Degrees is ALWAYS Twice the Number of Edges

The degree sequence of an undirected graph $G$ is a bracketed list of the degrees of all the vertices written in ascending order with repetition as necessary.

Example 5

2.2. Connected Graphs

A graph is said to be connected if it cannot be expressed as the union of two graphs. If a graph is not connected it is said to be disconnected. The graph on the left is connected as it is “in one piece” while the graph on the right is disconnected as it contains two distinct components. See Section 4 for an alternative definition of connected.

2.2.1. Cut-Points and Bridges

A vertex is a cut-vertex, if removal of that vertex (and the edges through it) disconnects the graph. A cut-vertex is also called a cut-point or an articulation point.

Example 6

In this section we briefly look at different types of graphs.

3.1. Regular Graphs

A graph $G$ is regular if all vertices of $G$ have the same degree. A regular graph where all vertices have degree $k$ is referred to as a $k$-regular graph.

Example 7

3.2. Complete Graphs

A complete graph, denoted $K_n$, is a graph with $n$ vertices all of which are adjacent to each other.

The complete graph $K_n$ is regular and each of the $n$ vertices has degree $n - 1$. Hence, the sum of the degrees is $n(n - 1)$ and by the Handshaking Lemma the number of edges in $K_n$ is, $\frac{n(n - 1)}{2}$

Exercise: Check the two properties stated above hold for the complete graphs shown.

3.3 Cycle Graph

A cycle on a graph starts at any vertex, travelling through the graph without repeating vertices or edges before ending on the start vertex. In 📷 Example 5, $BAEB$ and $AEDBA$ are both cycles while $AEDBEA$ is not a cycle as the vertex $E$ is repeated.

A cycle graph, denoted $C_n$, is a graph on $n$ vertices, $\{v_0, v_1, .\;\;\; ., v_{n-1}\}$ , with $n$ edges $\{v_0, v_1\}$, $(v_1, v_2\}$, $.\;\;\; .\;\;\; .$, $\{v_{n-1}, v_0\}$. Note that $C_n$ contains a single cycle through all the vertices.

Notes

(i). In a cycle graph every vertex has degree 2.

(ii). The graph $C_1$ contains a self-loop and we shall see later that a loop contributes two to the degree of the vertex. Hence, the vertex in $C_1$ has degree 2 ensuring that the Handshaking Lemma holds.

(iii). The graph $C_2$ contains parallel edges.

A graph that contains no loops or parallel edges is called a simple graph.

3.4. Bipartite Graphs

A bipartite graph, $G(V_1, V_2)$ is a graph whose vertices can be partitioned into two disjoint subsets $V_1$ and $V_2$, where no edge joins vertices that are in the same subset. A vertex in one of the subsets may be joined to all, some, or none of the vertices in the other subset – see the diagrams below. In the case where every vertex of $V_1$ is joined to every vertex of $V_2$ then $G$ is called a complete bipartite graph and is usually denoted $K_{r, s}$ . Here $r$ and $s$ represent the number of vertices in $V_1$ and $V_2$ respectively. A bipartite graph is usually shown with the two subsets as top and bottom rows of vertices or with the two subsets as left and right columns of vertices.

The graph on the right is the complete bipartite graph, $K_{2, 5}$ with $2 + 5 = 7$ vertices and $2 \times 5 = 10$ edges. In general, a complete bipartite graph $K_{r, s}$ has $r + s$ vertices and $r \times s$ edges.

A bipartite graph $K_{r, s}$ is regular if and only if $r = s$ . The complete bipartite graph $K_{3, 3}$ shown below is regular as each vertex has degree 3.

A complete bipartite graph of the form $K_{1, s}$ is called a star graph and $K_{1, 4}$ is shown below.

Example 8

3.5. Tree Graphs:

A forest is a graph containing no cycles and a connected forest is called a tree. Note that a graph on $n$ vertices has fewest edges when it is a tree (as it has no cycles) and most edges when it is a complete graph. Below is a forest with four components.

If the four components in the above forest are connected we obtain the tree below.

Theorem

Let $T$ be a graph with $n > 1$ vertices. The following statements are equivalent:

$T$ is a tree.

$T$ is cycle-free and has $n – 1$ edges.

$T$ is connected and has $n – 1$ edges.

$T$ is connected and contains no cycles.

$T$ is connected and each edge is a bridge.

Any two vertices of $T$ are connected by exactly one path.

$T$ contains no cycles, but the addition of any new edge creates exactly one cycle.

Note: From the above theorem it must be the case that a finite tree with $n$ vertices must have $n – 1$ edges.

3.6. Multigraphs

The diagram shows the graph $G = \{V, E\} = \{\{A, B, C, D\}, \{\{A, B\}, \{B, C\}, \{B, D\}, \{C, D\}, \{C, D\}, \{D, D\}\} \}$.

This is an example of a multigraph. A multigraph is a graph that allows the existence of loops and parallel (multiple) edges. Note that not all texts allow multigraphs to have loops and in the case when graphs include loops they are called pseudographs. We shall refer to a graph with parallel edges and/or loops as a multigraph.

A loop is an edge that links a vertex to itself. In the figure the edge $(D, D)$ is a loop and connects vertex $D$ to itself.

If two vertices are joined by more than one edge then these edges are called parallel edges. In the figure the two edges $(C, D)$ represent parallel edges.

Notes

(i). We define a loop to contribute 2 to the degree of a vertex so that the Handshaking Lemma holds for multigraphs. In the above figure vertex $D$ therefore has degree 5. The degree sum of the graph is $1 + 3 + 3 + 5 = 12$ which is twice the number of edges (6) as required by the Handshaking Lemma.

(ii). Some texts do not allow multigraphs to have loops.

A walk of length $k$ on a graph $G$ is an alternating sequence of vertices $( v_i )$ and edges $( e_i )$:

$v_0, e_1, v_1, e_2, v_2, e_3, \dots e_k, v_k$

where $v_i$ and $v_{i + 1}$ are both incident to $e_{i + 1}$. Note that the graph has $k + 1$ vertices and $k$ edges.

The length of a walk is the number of edges in the walk.

For convenience, and ease of reading, we omit edges and use only vertices so that the walk given above is written as $v_0, v_1, v_2, \dots ,v_{k-1}, v_k$.

Example 9

Now that we have defined the term path we can provide an alternative definition, to that given in Section 2.2, for a graph to be connected.

A graph is connected if given any two vertices $v_i$ and $v_j$ there is a path from $v_i$ to $v_j$ .

Returning to the example in Section 2.2, reproduced below for completeness, there is clearly a path between all the vertices in the graph on the left and so it is connected. However, in the graph on the right we are unable to, for example, find a path from vertex $S$ to vertex $P$ and so the graph is disconnected.

This section considers special ways of traversing graphs. Examples of graph traversal problems are the Königsberg bridges and Travelling Salesman problems.

5.1. Eulerian Graphs

Definition: An Euler circuit on a graph, $G$, is a circuit (closed trail) that uses every edge of $G$ exactly once. Note that we are allowed to use the same vertex multiple times, but we can only use each edge once. A graph is Eulerian if it has an Euler circuit.

Definition: An Euler trail through a graph, $G$ is an open trail that passes exactly once through each edge of $G$. We say that $G$ is semi-Eulerian if it has an Euler trail. Note that every Eulerian graph is semi-Eulerian.

Theorem: Let $G$ be a connected graph. Then $G$ is Eulerian if and only if every vertex of $G$ has even degree.

Corollary: A connected graph is semi-Eulerian if and only if there are $0$ or $2$ vertices of odd degree. Note that if a semi-Eulerian graph has two vertices of odd degree then any Euler trail must have one of them as its initial vertex and the other as its final vertex.

The table below provides simple rules that count the number of odd degree vertices in a graph to decide whether or not it has an Euler circuit or Euler trail.

No. of Odd Vertices	For a Connected Graph
0	There is at least one Euler circuit.
1	Not possible
2	No Euler circuit but at least 1 Euler trail.
More than 2	No Euler circuits or Euler traits.

Example 10

The following algorithm is optional but it provides a relatively simple method for finding an Euler circuit when one exists.

Fleury’s Algorithm (OPTIONAL)

If $G$ is an Eulerian graph then using the following procedure, known as Fleury’s Algorithm, it is always possible to construct an Euler circuit of $G$.

Starting at any vertex of $G$ traverse the edges of $G$ in an arbitrary manner according to the following rules:

(i). Erase edges as they are traversed and if any isolated vertices appear erase them.

(ii). At each step use a bridge only if there is no alternative.

Watch this video:

📹 Fleury's Algorthim

Note: Since every vertex in the Königsberg graph in 📷 Figure 2 has an odd degree it is not possible to find an Euler circuit of this graph. It is therefore impossible for someone to walk around the city in such a way that each bridge is crossed exactly once and they end up at their starting point.

5.2. Hamiltonian Graphs

Definition: A Hamiltonian cycle on a graph, $G$, is a cycle (closed path) that uses every vertex of $G$ exactly once. Note that we do not need to use all the edges. A graph is Hamiltonian if it has an Hamiltonian cycle.

Note that some texts call a Hamiltonian cycle a Hamiltonian circuit, i.e. a circuit which passes exactly once through each vertex of a graph. This definition is identical to the one above because a circuit which does not repeat vertices, apart from the starting vertex, is a cycle.

Definition: A trail that passes exactly once through each vertex of a graph $G$ and is not closed is called a Hamiltonian trail. We say that $G$ is semi-Hamiltonian. Note that every Hamiltonian graph is semi-Hamiltonian.

Note that while we have a theorem that provides necessary and sufficient conditions for a connected graph to be Eulerian (i.e. ‘$G$ is Eulerian if and only if every vertex of $G$ has even degree’) there is no similar characterisation for Hamiltonian graphs – this is one of the unsolved problems in graph theory. In general, it is much harder to find a Hamiltonian cycle than it is to find an Euler circuit.

Example 11

Notes

(i). The Travelling Salesman problem (TSP) searches for the most efficient (least total distance) Hamiltonian cycle a salesman can take so that each of n cities is visited. To date, no solution to the TSP has been found.

(ii). An Euler circuit traverses every edge in a graph exactly once, and may repeat vertices. A Hamiltonian cycle, on the other hand, visits each vertex in a graph exactly once but does not need to use every edge.