Discrete Math - The MKD Remix (Public Version)

A graph consists of a set of vertices and a set of edges. Each edge connects either two different vertices or one vertex to itself. Vertices are sometimes called nodes.

The following example illustrates many of these definitions.

Notice that in the example and definitions given so far, we’ve assumed that each edge is undirected: An edge represents a connection between its endpoints but does not indicate a direction of travel from one endpoint to the other endpoint. However, in some applications it is useful for a graph to use only directed edges that point from one endpoint to the other endpoint. A graph that has only directed edges is called a digraph, which is short for directed graph.

Most graphs discussed in this chapter will be (undirected) simple graphs, that is, graphs with no loops and no parallel edges.

This section describes a property of every undirected graph.

Recall that the degree of a vertex of a graph is the number of times the vertex occurs as an endpoint for all the edges in the graph. Keep in mind that the vertex of a loop counts twice because that vertex occurs as “both endpoints” of the loop.

Notice that the sum of the degrees of all the vertices is \(14\), which is equal to twice the number of edges, \(2 \cdot 7.\)

In fact, for any undirected graph with finitely many edges, the sum of the degrees of all vertices is equal to twice the number of edges (recalling that a loop’s endpoint will be counted twice.)

Recall that in a simple graph, there are no loops and no parallel edges (that is, you cannot have two different edges that connect the same pair of endpoints.) This means that for a simple graph, 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.” Graphs discussed in this textbook are assumed to be simple unless stated otherwise.

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 vertex \(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 vertex. The in-degree of a vertex \(w\) is the number of edges that have \(W\) as the terminal vertex.

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…​ .

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.

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.

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

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.

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

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. That is, two vertices are endpoints of an edge in the first graph if and only if the corresponding vertices are the endpoints of an edge in the second graph. Informally, you can think of two isomorphic graphs as a pair of graphs where a drawing of one graph can be relabeled and/or reshaped to obtain a drawing of the other graph (That is, the two graphs are really the same graph but have drawings that are labeled and/or shaped differently.)

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.

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.

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\), where for each integer value of \(i \leq n\) the endpoints of \(e_i\) are the vertices \(v_{i-1}\) and \(v_i.\) The integer \(n\) is called the length of the walk.

If we restrict ourselves to simple undirected graphs, there is at most one edge joining each pair of adjacent vertices, so a walk can be specified simply by listing the sequence of vertices \(v_0v_1\ldots v_n\) (That is, we don’t need to write down the edges.)

The distance \(d(u,v)\) between two vertices \(u\) and \(v\) in a graph \(G\) is the number of edges in a shortest path connecting them, assuming such a path exists.

A graph \(G\) is connected if there is a path between any pair of vertices.

In the previous example, the graph \(G\) can be treated as a union of two connected subgraphs, called the connected components of \(G.\) It can be proven by mathematical induction that any simple undirected graph that has a finite number of vertices can be written as a union of a finite number of connected components.

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 called 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 (Notice that some vertices are visited multiple times; it is the edges that must appear exactly once in an Euler path.) 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

Euler solved a famous problem about the seven bridges of Königsberg by representing the problem as a graph (with parallel edges.)

A cycle in a graph \(G\), is called 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 (Notice that some edges are used multiple times; it is the vertices, starting and ending vertex, that must appear exactly once in an Hamiltonian path.) The second graph is not Hamiltonian.

In some applications of graph theory, you need to find a "shortest path" between two vertices of a weighted graph. In the context, shortest may mean "of least distance" but could mean "of least cost" or something else, depending on what the edge weights represent.

Edsger Dijkstra published a paper in 1959 that describes an algorithm for finding the path of "minimum total weight" between two given vertices of a simple connected graph with weighted undirected edges.
Dijkstra’s original paper is also available in the ACM Digital Library at this link.

Here is a description of the algorithm, based on Dijkstra’s original.

Notice that the list \(E_{chosen}\) is constructed so that it contains edges for only one possible path between \(a\) and \(z,\) and that path must be a minimal-weight path.

Also notice if the loop condition is changed to "while there is a vertex that is not in \(V_{chosen}\)" then the algorithm’s output \(E_{chosen}\) will find the edges needed for a possible minimal-weight path between vertex \(a\) and any other vertex in the graph.

Question: What change would be needed to the input if you had a graph with unweighted edges and needed to find a path between \(a\) to \(z\) that uses the smallest number of edges possible?

This Wikipedia page has some animations that illustrate an alternate implementation of Dijkstra’s algorithm.

The Traveling Salesperson Problem (TSP) can be stated as “A traveling salesperson needs to start in the home city, visit each of a number of other cities, and then return to the home city. What path should the salesperson take so that the total distance traveled is the least possible?”

The TSP can be modeled using a graph. If there are \(n\) cities, you can represent each city as a vertex of the complete graph \(K_{n}\) and assign to each edge a weight equal to the distance between the cities at the endpoints. The TSP is solved by finding a Hamiltonian cycle of minimum total weight that visits each vertex exactly one.

Notice that if you choose a vertex (city) as the starting and ending point, then there are \(\frac{1}{2}(n-1)!\) different Hamiltonian cycles (The division by 2 represents that you could reverse the direction of the cycle without changing the total distance traveled.)

The brute-force solution examines every possible path and has time complexity \(O(n!),\) which is infeasible for even relatively small values of \(n.\) At present, there is no algorithm with polynomial worst-case time complexity that solves the TSP.

MORE TO COME!