A Simple Introduction to Graph Theory - Brian Heinold

1 A Simple Introduction to Graph Theoryab(1,a)c(8,d)d(3,b)e(2,b)f(5,d)g(6 ,f)(7,e)194125842951abcdef efbadgcabcgedf10|2020|2045|5020|200|525| 5010|2010|100|50|540|405|5 2018 Brian HeinoldLicensed under aCreative Commons Attribution-Noncommercial-Share Alike Unported LicenseiiPrefaceThese are notes I wrote up for my Graph Theory class in 2016. They contain most of the topics typically found ina Graph Theory course. There are proofs of a lot of the results, but not of everything. I ve designed these notes forstudents that don t have a lot of previous experience in math, so I spend some time explaining certain things inmore detail than is typical.

2 My writing style is also pretty you see anything wrong (including typos), please send me a note updated June 16, What is a Graph ? .. Common graphs .. Subgraphs .. Connectedness .. Other important terminology .. Graph isomorphism .. New graphs from old graphs ..102 Proofs, Constructions, Algorithms, and Basic results and proving things about graphs .. Constructions .. Graph Representations .. Algorithms .. Applications of graphs ..243 Bipartite Graphs and Bipartite graphs .. Trees .. Spanning trees.

3 Minimum spanning trees .. Shortest paths ..384 Eulerian and Hamiltonian Eulerian circuits .. Hamiltonian cycles .. Showing a Graph has a Hamiltonian cycle .. The Traveling Salesman Problem and NP Completeness ..525 Definitions and examples .. Properties .. Applications .. Edge coloring .. Further details on coloring ..666 Planar Definitions and properties .. More on planarity .. Embedding graphs on surfaces ..767 Matchings and Definitions and properties .. Bipartite matching and the Augmenting Path Algorithm.

4 More on bipartite matchings .. Hall s theorem .. Weighted bipartite matching .. Stable matching .. More about matching ..928 Definitions and properties .. Connectedness of digraphs .. Directed acyclic graphs .. Tournaments ..989 Definitions and properties .. Menger s theorem .. Network flow ..102 Epilogue and Bibliography108 Exercises109 Exercises for Chapter 1 ..109 Exercises for Chapter 2 ..112 Exercises for Chapter 3 ..114 Exercises for Chapter 4 ..118 Exercises for Chapter 5 ..121 Exercises for Chapter 6.

5 123 Exercises for Chapter 7 ..124 Exercises for Chapter 8 ..126 Exercises for Chapter 9 ..127 Chapter What is a Graph ?Graphs are networks of points and lines, like the ones shown are useful in modeling all sorts of real world things, as we will see, as well as being interesting in their ownright. While the figure above hopefully gives us a reasonably good idea of what a Graph is, it is good to give aformal definition to resolve any a pair(V,E), where V is a set of objects calledverticesand E is a set of two element subsetsof V a Graph is defined purely in terms of what its vertices (points) are, and which vertices are connected to whichother vertices.

6 Each edge (line) is defined by its two endpoints. It doesn t matter how you draw the Graph ; allthat matters is what is connected to instance, shown below are several ways of drawing the same Graph . Notice that all three have the samestructure of a string of vertices connected in a the second and third examples above, we could imagine moving vertices around in order to straighten out the Graph to look like the first example. Notice in the third example that edges are allowed to cross over each fact, some graphs can t be drawn without some edges crossing. Edges are also allowed to curve.

7 Rememberthat we are only concerned with which vertices are connected to which other ones. We don t care exactly howthe edges are fact, we don t even have to draw a Graph at all. The Graph above can be simply defined by saying its verticesare the setV={a,b,c,d,e}and its edges are the setE={a b,bc,cd,d e}. However, we will usually draw ourgraphs instead of defining them with sets like 1. BASICS2 Important terminology and notationThe terms and notations below will show up repeatedly. We will usually denote vertices with single letters likeuorv. We will denote edges with pairs of letters, likeuvto denote the edge between verticesuandv.

8 We will denote graphs with capital letters, likeGorH. Two vertices that are connected by an edge are said to beadjacent. An edge is said to beincidenton its two endpoints. Theneighborsof a vertex are the vertices it is adjacent to. Thedegreeof a vertex is the number of edges it is an endpoint of. The notation deg(v)denotes the degreeof vertexv. The set of vertices of a graphG, called itsvertex set, is denoted byV(G). Similarly, theedge setof a graphis denoted byE(G).For example, in the Graph below, the bottommost edge is between verticesdande. We denote it as edged e.

9 Thatedge is incident ondande. Vertexdis adjacent to vertexe, as well as to verticesbandc. The neighbors ofdareb,c, ande. Anddhas degree , in these notes, all graphs are assumed to be finite and nonempty. Infinite graphs are interesting, but addquite a few complications that we won t want to bother with is possible to have an edge from a vertex to itself. This is called aloop. It is also possible to have multiple edgesbetween the same vertices. We use the termmultiple edgeto refer to edges that share the same endpoints. In thefigure below, there is a loop at vertexaand multiple edges (three of them) and multiple edges cause problems for certain things in Graph Theory , so we often don t want them.

10 A graphwhich has no loops and multiple edges is called asimple Graph . A Graph which may have loops and multiple edgesis called amultigraph. In these notes, we will often use the termgraph, hoping it will be clear from the contextwhether loops and multiple edges are allowed. We will use the termssimple graphandmultigraphwhen we wantto be explicitly that loops and multiple edges don t fit our earlier definition of edges as being two-element subsets of thevertex set. Instead, a multigraph is defined as a triple consisting of a vertex set, an edge set, and a relation thatassigns each edge two vertices, which may or may not be also that loops count twice toward the degree of a 1.