Discrete Math - The MKD Remix

14.1. Introduction and Basic Definitions

A graph consists of a set of vertices (also called nodes ) and a set of edges, where each edge connects either two different vertices or one vertex to itself.

For each edge, its endpoints are the vertices that it connects. The edge is said to be incident with each endpoint, and to connect the endpoints.
If an edge has only one endpoint, it is called a loop.
If two or more edges connect the same endpoints (or endpoint if the edges are loops), the graph is called a multigraph. Two edges that have the same endpoints are called parallel edges.
Two vertices are adjacent if they are the endpoints of at least one edge. Adjacent vertices are also called neighbors.
The degree of a vertex \(v\) is the number of edges in the graph \(G\) containing the vertex \(v.\)
An isolated vertex is a vertex that is not an endpoint of any edge.
A simple graph is a graph that has no loops and does not have two or more edges that connect the same endpoints.

Example 1

The graph shown has 7 vertices and 7 edges.

This is one graph that is made up of three separate connected components (Connectivity will be defined in detail later in the chapter, but is introduced informally here).

One connected component contains the vertices \(A\) and \(C\) and two edges that connect them.
A second connected component contains the vertices \(B\), \(D\), \(E\), and \(F\) and the edges that are incident to those vertices.
A third connected component contains the single isolated vertex \(G\) and no edges.

In the second connected component, the graph is drawn so that the edge with endpoints \(B\) and \(F\) and the edge with endpoints \(D\) and \(E\) cross, but the point of intersection is ignored because it is not a vertex. We could redraw this graph so that the two edges do not cross; for example, we could move \(E\) inside the triangle. However, there are some graphs which cannot be drawn in 2 dimensions without some edge crossings.

This graph is a multigraph because there are multiple edges that connect the pair of vertices \(\{A,C\}\).

This graph is not simple because (1) it contains a loop and (2) it has a pair of vertices that are connected by two different edges.

14.2. Simple Graphs

A simple graph is a graph that has no loops and no parallel edges (that is, no two edges can connect the same endpoints.) This means that each edge is determined by its two distinct endpoints. This allows us to give a relatively simple but formal set-theoretic definition of "simple graph". This formal definition can be useful if you need to implement a simple graph in code. Graphs discussed in this textbook are assumed to be simple unless stated otherwise.

14.2.1. A Formal Definition

A simple graph \(G=\left(V,\ E\right)\) is an ordered pair consisting of a set \(V\) of objects called vertices (also called nodes ) and a set \(E\) of objects called edges . An edge \(e\in\ E\) is a set of the form \(e=\left\{x,y\right\}\), where the vertices \(x\) and \(y\) are two different elements of \(V\). The two vertices \(x\) and \(y\) in the edge \(e=\left\{x,y\right\}\) are said to be adjacent or connected or neighbors , and \(x\) and \(y\) are called the endpoints of the edge \(e\).

Example 2 - a simple graph.

The graph shown has vertex set \(\left\{A,\ B,\ C,\ D,\ E,\ F\right\}\) and edge set \( \{\{A,C\},\{A,D\},\{B,D\}\{B,F\},\{C,F\},\{D,F\},\{E,F\}\}.\)

Example 3

The degrees of each of the vertices in the undirected graph \(G\) with vertex set \(V=\{A,B,C,D,E,F,G\}\) and edge set \(E=\{\{A,C\},\{A,D\},\{B,D\}\{B,F\},\{C,F\},\{D,F\},\{F,G\}\) are,

\(d\left(A\right)=2\)

\(d\left(B\right)=2\)

\(d\left(C\right)=2\)

\(d\left(D\right)=3\)

\(d\left(E\right)=0\)

\(d\left(F\right)=4\)

\(d\left(G\right)=1\)

Notice that the sum of all the degrees \(d\left(A\right)+\ d\left(B\right)\ +\ d\left(C\right)+\ \ d\left(D\right)\ \ +d\left(E\right)+\ d\left(F\right) + d\left(G\right)=14\), which is is twice the number of edges, \(2 \cdot \left|E\right|=7\). In fact, this is true for any undirected graph with finitely many edges as long as any loops are counted twice. This result is called the Handshaking Theorem. A formal proof of the Handshaking Lemma can be written using mathematical induction on the predicate \(P(n):\) "If graph \(G\) has \(n\) edges, then the sum of the degrees of the vertices of \(G\) is equal to \(2n.\)"

Handshaking Theorem

The sum of the degrees of the vertices of a graph \(G=\left(V,\ E\right)\) is equal to twice the number of edges in \(G\). That is, \(\displaystyle \sum_{v\in V}{d\left(v\right)=2\ \left|E\right|}\).

A useful consequence of this to keep in mind is that the sum of the degrees of a graph is always even.

14.3. Directed Graphs

The main focus of this chapter will be undirected simple graphs, but we will briefly discuss directed graphs in this section.

A directed graph (or digraph ) is a graph in which the edges are directed from one vertex to another vertex. Each edge has an initial vertex \(u\) and a terminal index \(v;\) the edge is drawn as an arrow pointing from \(u\) to \(v.\)

The out-degree of a vertex \(w\) is the number of edges that have \(w\) as the initial index. The in-degree of a vertex \(w\) is the number of edges that have \(W\) as the terminal index.

Example 4 - A directed graph.

The graph \(G=(V,E)\) with vertex set \(V=\{A,B,C,D,E,F\}\) and edge set \(E=\{ (A,C),(D,A),(B,D),(F,B),(C,F),(D,F),(F,E) \}\). The first coordinate of each edge is the initial vertex and the second coordinate is the terminal vertex.

Example 5 - The game "rock, paper, scissors"

The graph \(G=(V,E)\) with vertex set \(V = \{ \text{"rock", "paper", "scissors"} \}\) and edge set \(E = \{ \text{("rock", "paper"), ("paper", "scissors"), ("scissors", "rock")} \}\) can be used to represent the game "rock, paper, scissors."

Each directed edge has for its initial vertex the loser and for its terminal edge the winner.

14.3.1. Simple Directed Graphs

We can give a formal set-theoretic definition of simple directed graph as well. To indicate the directed edges, ordered pairs of vertices are used instead of 2-element sets.

A simple directed graph \(G=\left(V,\ E\right)\) is an ordered pair consisting of a set \(V\) of objects called vertices (or nodes ) and a set \(E\) of objects called edges . A directed edge \(e\in\ E\) is an ordered pair of the form \(e=\left(x,y\right)\), where the vertices \(x\) and \(y\) are two different elements of \(V\). Vertex \(x\) is the initial vertex of \(e\) and vertex \(y\) is the terminal vertex of edge \(e\).

14.4. Examples of Simple Graphs

In this section presents several classes of graphs.

The complete graph \(K_n\) is the simple graph with \(n\) vertices such that any two vertices are adjacent, that is, every pair of vertices are the endpoints of an edge. The image shows \(K_{4},\) the complete graph on 4 vertices. Click here to see images of \(K_{n}\) for the positive integers that are less than or equal to \(12.\)

The n-cube \(Q_{n}\) can be described as the graph that has vertex set consisting of the \(2^{n}\) bitstrings of length \(n,\) and edges such that two vertices are adjacent if and only if the bitstrings differ in exactly one bit position. The image shows the three graphs \(Q_{1},\) \(Q_{2},\) and \(Q_{3};\) these graphs can be used as a way to represent the power sets of sets that have \(1,\) \(2,\) and \(3\) elements, respectively. Notice that \(Q_{2}\) can be drawn as a square and that \(Q_{3}\) can be represented as a cube in \(3\)-dimensional space (or by a drawing of a cube in a \(2\)-dimensional plane.)

A bipartite graph is a simple graph whose set of vertices can be partitioned into two disjoint nonempty sets such that every vertex is in exactly one of the two sets and every edge has one endpoint in each of the two sets. One way to think of a bipartite graph is that each vertex can be assigned one of two colors so that every edge must connect vertices of different colors. Notice that \(Q_{1},\) \(Q_{2},\) and \(Q_{3}\) are all examples of bipartite graphs (Question: Is \(Q_{n}\) a bipartite graph for every natural number \(n?\) Why or why not?)

This image shows the graph \(K_{2,3}\) and is another example of a bipartite graph. Notice that \(K_{2,3}\) has an additional property: Every pair of vertices \(\{a, b \}\) with \(a\) in the set of \(2\) "upper" vertices and \(b\) in the set of \(3\) "lower" vertices are the endpoints of an edge. A bipartite graph that has this additional property is called a complete bipartite graph. In general, the symbol \(K_{m,n}\) represents the complete bipartite graph that has two disjoint sets of vertices, one of cardinality \(|m|\) and the other of cardinality \(|n|,\) such that every pair of vertices that come from the different sets are joined by an edge. Notice that \(Q_{1} = K_{1,1}\) and \(Q_{2} = K_{2,2}\) are complete bipartite graphs, but that \(Q_{3}\) is not a complete bipartite graph because, for example, there is no edge joining \(000\) and \(111.\)
NOTE: The phrase "complete bipartite" needs to be read as a single term used to indicate that a bipartite graph has all the edges it can possibly have. For example, \(K_{2,3}\) is a bipartite graph such that if you tried to enlarge it by inserting an additional edge into the graph, that edge would join either the \(2\) "upper" vertices, \(2\) of the "lower" vertices, or \(2\) vertices that are already joined; in this sense, \(K_{2,3}\) is "complete" as a bipartite graph. \(K_{2,3}\) is not a "complete graph" in the sense of the earlier example in this section. In fact, since a "complete graph" must contain an edge for every pair of distinct vertices, the only graph that can be both a "complete graph" and a "complete bipartite graph" is \(Q_{1} = K_{2} = K_{1,1}.\) Mathematicians recycle and reuse a lot of words… .

14.5. Representing Simple Graphs

In addition to the vertex-edge drawing, a simple graph can be represented in other ways that are more useful for computing.

First, recall that if \(u\) is a vertex of a simple graph, then vertex \(v\) is said to be adjacent to \(u\) if and only if \(\{u, v \}\) are the endpoints of an edge of the graph.

One way to represent a simple graph is by using an adjacency list. This list can be written as a table, where each row has two columns. In each row, the entry in the first column is a single vertex \(v\) and the entry in the second column is a list of all vertices of the graph that are adjacent to \(v.\)

Another way to represent a simple graph is by using an adjacency matrix. The adjacency matrix of a simple graph represents the graph in table form, and contains an entry for each pair of vertices. For each vertex of the graph, there is a row and also a column. If vertices \(u\) and \(v\) are adjacent (that is, connected by some edge), then the adjacency matrix will contain a \(1\) in the position that corresponds to the row for \(u\) and the column for \(v,\) otherwise the matrix contains a \(0\) at that postion. The next example may help make this more clear.

Example 6 - Representing A Simple Graph

The graph with vertex set \(\left\{A,\ B,\ C,\ D,\ E,\ F\right\}\) and edge set \(\{\{A,C\},\{A,D\},\{B,D\}\{B,F\},\{C,F\},\{D,F\},\{E,F\}\}\) can be represented by

the drawing

or the adjacency list

Vertex	Adjacent Vertices
A	C, D
B	D, F
C	A, F
D	A, B, F
E	F
F	B, C, D, E

Vertex

Adjacent Vertices

A

C, D

B

D, F

C

A, F

D

A, B, F

E

F

B, C, D, E

or the adjacency matrix

\(\mathbf{M}=\left(\begin{matrix}0&0&1&1&0&0\\0&0&0&1&0&1\\1&0&0&0&0&1\\1&1&0&0&0&1\\0&0&0&0&0&1\\0&1&1&1&1&0\\\end{matrix}\right)\)
For example, in matrix \(\mathbf{M}\) the rows, from top to bottom correspond to the vertices \(A,\ B,\ C,\ D,\ E,\ F\) and the columns, from left to right, corespond to vertices \(A,\ B,\ C,\ D,\ E,\ F.\) The values in row 3, which corresponds to vertex \(C\), indicate whether the vertex for that column is adjacent to \(C.\) If we use the symbol \(M_{r,c}\) to stand for the value in row \(r\) and column \(c,\) then \(M_{3,5} = 0\) because there is no edge in the graph with endpoints \(C\) and \(E,\) and \(M_{3,6} = 1\) because there is an edge in the graph with endpoints \(C\) and \(F\).

14.6. Weighted Graphs

In some applications, each edge of a graph has a weight, which is some nonnegative number. The weight could represent the physical distance between the two endpoint nodes, or could represent the cost to travel or transmit data between the endpoint nodes.

You can use an adjacency matrix to describe a weighted graph, but instead of using a \(1\) to represent that there is an edge between two vertices you place the the weight of the edge in the correct position of the adjacency matrix, as shown in the following example.

Example 7 - Weighted Graph

Consider the following weighted simple graph

The adjacency matrix of this weighted graph is \( \left(\begin{matrix}0&2&5&0\\2&0&3&0\\5&3&0&1\\0&0&1&0\\\end{matrix}\right). \)

14.7. Creating New Graphs From Old Graphs

Given a set of one or more graphs, there are several ways to create new graphs using the graphs in the set.

14.7.1. Subgraphs

Given a simple graph \(G,\) you can form a subgraph \(H\) by choosing a subset of the vertices of \(G\) along with a subset of the edges of \(G\) such that each edge has endpoints in the set of vertices you chose. That is, \(H\) is a subgraph of \(G\) if \(H\) is a graph such that every vertex of \(H\) is a vertex of \(G\) and every edge of \(H\) is a vertex of \(G.\)
More formally, \(H = (V_{H}, E_{H})\) is a subgraph of \(G = (V,E)\) if and only if all three of the following statements are True: \(V_{H} \subseteq V,\) \(E_{H} \subseteq E,\) and for every edge \(e \in E_{H}\) the endpoints of \(e\) are in \(V_{H}.\)

If \(v\) is a vertex of \(G,\) we denote by \(G-v\) , the subgraph obtained from \(G\) by removing the vertex \(v\) along with all edges in \(E\) that have \(v\) as an endpoint.

The image shows a graph \(G\), and the subgraph \(G-d\) formed by removing the vertex \(d\).

In the same way, you can obtain a subgraph by removing multiple vertices along with the edges associated with the removed vertices. The subgraph obtained is called the subgraph induced by removing those vertices.

Example 8

Below is a graph \(G(V,E)\) and the subgraph obtained by \(V-\{a,d\}\), called the induced subgraph \(G-\{a,d\}\), with a slight abuse of notation

14.7.2. Unions and Intersections Of Graphs

Given two simple graphs \(G_{1}\) and \(G_{2}\), you can form the union of the graphs by taking the union of the two sets of vertices to get a new set of vertices, and taking the union of the two sets of edges to get a new set of edges. Notice that any edge that is in both graphs will only appear once in the new graph because you took the union of the sets of edges, that is, you can’t create parallel edges by forming the union.

In the same way, you can form the intersection of two simple graphs by taking the intersection of the two sets of vertices to get a new set of vertices, and taking the intersection of the two sets of edges to get a new set of edges.

14.8. Graph Isomorphism

Recall that a graph is determined by its set of vertices and how those vertices are connected by edges, but not the drawing you use to represent the graph.

Example 9 - The Same Graph Can Be Drawn In More Than One Way

Consider the two graphs shown in the image.

Notice that these two graphs are different-looking drawings of the same graph that has vertex set \(\{ A, B, C, D\}\) and edge set \(\{\{A,B\},\{A,C\},\{A,D\}\{B,C\},\{B,D\},\{C,D\}\}.\) Also, notice that the drawing on the left appeared earlier in the chapter, but with unlabeled vertices: This is a drawing of \(K_{4},\) the complete graph on \(4\) vertices.

Notice that using either the adjacency list

Vertex	Adjacent Vertices
A	B, C, D
B	A, C, D
C	A, B, D
D	A, B, C

Vertex

Adjacent Vertices

A

B, C, D

B

A, C, D

C

A, B, D

D

A, B, C

or the adajcency matrix \[\left(\begin{matrix}0&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&0\\\end{matrix}\right)\] makes it easier to see that the two drawings represent the exact same graph.

You can imagine the graph on the right being the result of dragging the vertex \(C\) inside the "triangle" with vertices \(A,\) \(B,\) and \(D.\)

Sometimes, different graphs may be essentially the same graph, as in the next example.

Example 10 - Two Graphs That Are Essentially The Same Graph

Consider the two graphs, each with \(4\) vertices and \(6\) edges, shown in the image.

These graphs are not equal since the graph on the left has vertex set \(\{ A, B, C, D\}\) and the graph on the right has vertex set \(\{ W, X, Y, Z\}.\) However, by comparing the graph on the right to the one on the right in the previous example, you can see that there is a one-to-one correspondence between the two sets of vertices that preserves adjacency (that is, if two vertices in the upper row are endpoints of an edge of the graph on the left, then the corresponding vertices in the lower row are endpoints of an edge of the graph on the right.)

A one-to-one correspondence between the set of vertices of two simple graphs that preserves adjacency is called a graph isomorphism, and the two graphs are said to be isomorphic. Informally, you can think of two isomorphic graphs as a pair of graphs where one graph can be relabeled and/or reshaped to obtain the other graph (That is, the two graphs are the same graph but have drawings that are labeled and/or shaped differently.)

Example 11 - Using Graph Isomorphism

Using graph isomorphisms can help identify properties of a graph.

The three graphs in the image are isomorphic; it is an exercise for you to write out the one-to-one correspondences.

You Try

Write out the one-to-one correspondences between the sets of vertices that define the graph isomorphisms.

Once you have shown that the three graphs are isomorphic, you can use the fact that they are different representations of the same graph. For example,

It is not immediately clear that the graphs on the left and right are bipartite, but the arrangement of the vertices in the middle graph into "upper" and "lower" rows makes this easy to see.
Also, it is not immediately clear that the graph in the middle or the graph on the right is planar (that is, the graph can be redrawn in a \(2\)-dimension plane so that no edges cross) but this is obvious for the graph on the left.
Note: This textbook does not discuss planar graphs in detail, but it is worth mentioning that it can be proven that neither \(K_{5}\) nor \(K_{3,3}\) is planar. If you’d like to learn more about planar graphs, one source is the section "Planar Graphs" in Oscar Levin’s Discrete Mathematics: An Open Introduction, 3rd edition.

Challenge

Write out the adjacency matrix for each of the three graphs, using alphabetical order of the vertex labels, then identify a connection between the three adjacency matrices.

Hint

Look for rows and columns in the different matrices that are identical. The order of the rows and columns would change if you use non-alphabetical reorderings of vertices that correspond to the graph isomorphisms you wrote for the "You try" exercise above.

14.9. Graph Coloring

In some contexts, it can be useful to partition either the set of vertices or the set of edges of a graph into disjoint subsets to make it easier to understand the graph and the network it represents. This act of partitioning is usually referred to as "coloring" since using different colors can make it easy to see and interpret the properties of the partition when the graph is drawn. Notice that you could instead create the partition by assigning labels like "group 1," "group 2," and so on, to each vertex (or edge.)

For example, the image shows a graph called the Petersen graph with its vertex set partitioned into 3 subsets so that each edge’s endpoints are in two different subsets of the partition (That is, each edge’s endpoints have different colors.)
Image credit: "Petersen_graph_3-coloring.svg" by Д.Ильин. The copyright holder of this work has released this work into the public domain. This applies worldwide.

The next example discusses an application of vertex coloring.

Example 12 - Redrawing a Map as a Graph

The following image represents a "map" showing four countries; the blue region represents one country (not a body of water) that is surrounded by three other countries.

The map can be represented as a graph with vertices colored to match the regions, as shown on the right. If it helps you to connect the graph to the map, imagine that each vertex represents a capital city of the corresponding country.

This way of representing a map was used to prove the Four Color Theorem which states, roughly, that

Four Color Theorem

Any map of countries that can be drawn in a plane such that
(1) every country has a color and
(2) no two adjacent countries have the same color
requires at most four different colors.
In this context "two adjacent countries" share a border that is not just a single point.

The first proof of the theorem was announced in 1976, and a corrected version of the first proof was published in 1989 after some errors were fixed (Yes, professional mathematicians do make mistakes!) The proof was considered controversial by many mathematicians at the time because it was the first major computer-assisted proof: Over one thousand five hundred different cases needed to be checked!

In other contexts, it is more appropriate to use edge coloring. That is, each edge of the graph is assigned a color so that the set of edges is partitioned into disjoint subsets. For example, the graph in the image shows that the complete bipartite graph \(K_{4,4}\) can be partitioned as a union of 3 disjoint graphs called forests (Forests are defined later in this textbook, in the Trees chapter.)
Image credit: "K44 arboricity.svg" by David Eppstein. The copyright holder of this work has released this work into the public domain. This applies worldwide.

14.10. Connectivity, Eulerian Graphs, and Hamiltonian Graphs

A walk on a graph \(G=\left(V,E\right)\) is a finite, non-empty, alternating sequence of vertices and edges of the form, \(v_0e_1v_1e_2\ldots e_nv_n\), with vertices \(v_i\in V\) and edges \(e_i\in E\).

We will focus on simple graphs. For simple graphs, there is at most one edge joining adjacent vertices, so we can omit the edges from the sequence and instead write \(v_0v_1\ldots v_n.\)

A trail is a walk that does not repeat an edge. That is, all edges in a trail are distinct.
A path is a trail that does not repeat a vertex.
The distance between two vertices, \(u\) and \(v\), denoted \(d(u,v)\), is the number of edges in a shortest path connecting them.
A cycle is a non-empty trail in which the only repeating vertices are the beginning and ending vertices, \(v_0=v_n\).

Example 13 - Trails, Paths, and Cycles

In the graphs below the first shows a trail \(CFDBFE\). It is not a path since the vertex \(F\) is repeated. The second shows a path \(CADFB\), and the third a cycle \(CADFC\). Also note the following distances, \(d(A,D)=1\), while \(d(A,F)=2\), and \(d(A,E)=3\).

A graph is connected if there is a path from each vertex to every other vertex.

Example 14 - A graph that is not connected

The graph \(G\) below is not connected since, as just one example, there is no path from vertex \(a\) to vertex \(e.\)

\(G\) has adjacency matrix

\( \left(\begin{matrix}0&1&1&0&0\\1&0&1&0&0\\1&1&0&0&0\\0&0&0&0&1\\0&0&0&1&0\\\end{matrix}\right). \)

14.10.1. Eulerian Graphs

An Euler path on a graph is a path that uses each edge of the graph exactly once.

An Euler circuit (also called an Eulerian trail ) is a closed trail containing each edge of the graph \(G\) exactly once and returning to the start vertex. A graph with an Euler circuit is considered Eulerian or is said to be an Eulerian graph .

In the following, the first graph is Eulerian. The sequence of edges \(e_1 e_2 e_3 e_4 e_5 e_6 e_7\) describes an Euler circuit. The second graph is not an Eulerian graph. Convince yourself of this fact by looking at all necessary trails or closed trails.

The following are useful characterizations of graphs with Euler circuits and Euler paths and are due to Leonhard Euler

Theorem on Euler Circuits and Euler Paths

A finite connected graph has an Euler circuit if and only if each vertex has even degree.
A finite connected graph has an Euler path if and only if it has at most two vertices with odd degree.

14.10.2. Hamiltonian Graphs

A cycle in a graph \(G\), is said to be a Hamiltonian cycle if every vertex, except for the starting and ending vertex, is visited exactly once.

A graph is Hamiltonian , or said to be a Hamiltonian graph , if it contains a Hamiltonian cycle.

The following graph is Hamiltonian and shows a Hamiltonian cycle \(ABCDA\), highlighted, while the second graph is not Hamiltonian.

While we have the Euler Theorem to tell us which graphs are Eulerian or not, there are no comparable simple criteria to determine if graphs are Hamiltonian or not. We do have the following sufficient criterion due to Paul Dirac.

Theorem (Dirac) on Hamiltonian graphs

A simple graph, with \(n≥3\) vertices, is Hamiltonian if every vertex \(v\) has degree \(d(v)\geq \frac{n}{2}\).

14.11. Finding A Shortest Path: Dijkstra’s Algorithm

COMING SOON!

14.11.1. Traveling Salesperson Problem (TSP)