CHAPTER 6Introduction to Graph Theory1. Introduction to Graphs1.1. Simple Graphs.Definition 1.1.1. A simple graph (V, E) consists of a nonempty set represent-ing vertices, V , and a set of unordered pairs of elements of V representing edges, E.A simple graph has• no arrows,• no loops, and• cannot have multiple edges joining vertices.DiscussionGraphs offer a convenient way to represent various kinds of mathematical objects.Essentially, any graph is made up of two sets, a set of vertices and a set of edges.Depending on the particular situation we are trying to represent, however, we maywish to impose restrictions on the type of edges we allow. For some problems we willwant the edges to be directed from one vertex to another; whereas, in others the edgesare undirected. We begin our discussion with undirected graphs.The most basic graph is the simple graph as defined above. Since the edges ofa simple graph are undirected, they are represented by unordered pairs of verticesrather than ordered pairs. For example, if V = {a, b, c}, then {a, b} = {b, a} wouldrepresent the same edge.Exercise 1.1.1. If a simple graph G has 5 vertices, what is the maximum numberof edges that G can have?1.2. Examples.Example 1.2.1. V = {v1, v2, v3, v4} E = {{v1v2}, {v1, v3}, {v2, v3}, {v2, v4}}1781. INTRODUCTION TO GRAPHS 179v1v2v3v4Example 1.2.2. V = {a, b, c}, E = {{a, b}, {b, c}, {a, c}}a bc1.3. Multigraphs. Definition: A multigraph is a set of vertices, V , a set ofedges, E, and a functionf : E → {{u, v} : u, v ∈ V and u 6= v}.If e1, e2∈ E are such that f(e1) = f(e2), then we say e1and e2are multiple orparallel edges.Example 1.3.1. V = {a, b, c, d}, E = {e1, e2, . . . , e6}, f : E → {{u, v} : u, v ∈V and u 6= v} is defined as follows.e e1e2e3e4e5e6f(e) {a, c} {a, c} {a, b} {c, b} {b, d} {b, d}1. INTRODUCTION TO GRAPHS 180e1e2e3e4e5e6abcdDiscussionIn Example 1.3.1 e1and e2are parallel edges, but the edges e2and e5are notcalled parallel edges.Exercise 1.3.1. Find all the parallel edges Example 1.3.1.Notice that a multigraph allows for multiple edges between a pair of vertices, butdoes not allow for loops. In some applications it may be desirable to illustrate allthe connections between the vertices. Say for example, in a network there may bemultiple wires connecting the same units.1.4. Pseudograph.Definition 1.4.1. A pseudograph is a set of vertices, V , a set of edges, E, anda function f : E → {{u, v} : u, v ∈ V }. If e ∈ E is such that f(e) = {u, u} = {u},then we say e is a loop.Example 1.4.1. V = {a, b, c, d}, E = {e1, e2, . . . , e8},f : E → {{u, v} : u, v ∈ V }is defined as follows.e e1e2e3e4e5e6e7e8f(e) {a, c} {a, c} {a, b} {c, b} {b, d} {b, d} {a} {d}1. INTRODUCTION TO GRAPHS 181e1e2e3e4e5e6abcde7e8DiscussionThe pseudograph adds the possibility of loops. For example, a diagnostic line maybe used in a network, which is a line connecting a computer to itself.1.5. Directed Graph.Definition 1.5.1. A directed graph (V, E) consists of a set of vertices, V , anda set of directed edges, E. The elements of E are ordered pairs of vertices.Example 1.5.1. V = {a, b, c, d},E = {(a, c), (c, a), (a, b), (c, b), (b, d), (d, b), (a, a), (d, d)},1. INTRODUCTION TO GRAPHS 182e1e2e3e4e5e6abcde7e8DiscussionA directed graph, or digraph, allows loops and allows two edges joining the samevertex, but going in the opposite direction. More than one edge going in the samedirection between vertices, however, is not allowed. A directed edge is defined byan ordered pair rather than an unordered pair. That is, the ordered pair (a, b) isdifferent from the ordered pair (b, a), while the unordered pair {a, b} = {b, a}. Becareful of the notation you use when writing an edge.Exercise 1.5.1. If a directed graph G has 5 vertices, what is the maximum numberof (directed) edges of G?1.6. Directed Multigraph.Definition 1.6.1. A directed multigraph (V, E) consists of vertices, V , andedges, E, and a functionf : E → V ×V = {(u, v)|u, v ∈ V }.The edges e1and e2are multiple edges if f(e1) = f(e2)Example 1.6.1. V = {a, b, c, d}, E = {e1, e2, . . . , e10},f : E → {(u, v) : u, v ∈ V }is defined as follows.e e1e2e3e4e5e6e7e8e9e10f(e) (a, c) (c, a) (a, b) (c, b) (b, d) (d, b) (a, a) (d, d) (a, b) (b, d)1. INTRODUCTION TO GRAPHS 183e1e2e3e4e5e6abcde7e8e9e10DiscussionNotice the difference between a directed graph and a directed multigraph: a di-rected graph allows more than one edge to connect the same two vertices as long asthey have opposite directions; whereas, no such restriction is placed on the edges ofa directed multigraph.Exercise 1.6.1. Give all the multiple edges in Example 1.6.1.1.7. Graph Isomorphism.Definition 1.7.1. Let G1= (V, E) and G2= (U, F ) be simple graphs. The graphsG1and G2are isomorphic if there exists a bijectionf : V → Usuch that for all v1, v2∈ V , v1and v2are adjacent in G1if and only if f(v1) andf(v2) are adjacent in G2.Definition 1.7.2. If f is a bijection as described above, then f is called an iso-morphism between G1and G2, and we often writef : G1→ G2.DiscussionThere are several notations that are used to represent an isomorphism. We willuse a common notation G1' G2to mean that G1is isomorphic to G2.Trying to construct an isomorphism between graphs can be a very difficult problemin general. If simple graphs G1and G2are isomorphic, then, clearly, they must have1. INTRODUCTION TO GRAPHS 184the same number of vertices. As the next exercise shows, G1and G2must also havethe same number of edges. Having the same number of vertices and edges,however, is in no way sufficient for graphs G1and G2to be isomorphic.Often to prove existence of an isomorphism between two graphs one must actuallyconstruct the isomorphism.Exercise 1.7.1. Prove that if simple graphs G1and G2are isomorphic, then G1and G2have the same number of edges.Example 1.7.1. The graphs G1and G2below are isomorphic. The bijection isdefined by f (vi) = ui.v1v2v4v3G1G2u2u3u1u4Example 1.7.1 illustrates a situation in which it is very easy to construct anisomorphism. The graph G2is merely an alteration of G1obtained by moving one ofthe edges so it goes around rather than crossing over another edge and relabeling itsvertices.One way to visualize when two graphs are isomorphic is to imagine that all thevertices are beads and each edge is represented by a sting with each end tied to thebeads that represents its endpoints. If you pick one or more beads up and place it inanother location without untying the strings, you obtain a