Graph Theory - University of Notre Dame

1 1 Graph Theory Begin at the beginning, the King said, gravely, and go on till youcome to the end; then stop. Lewis Carroll,Alice in WonderlandThe Pregolya River passes through a city once known as K onigsberg. In the 1700sseven bridges were situated across this river in a manner similar to what you seein Figure The city s residents enjoyed strolling on these bridges, but, as hardas they tried, no resident of the city was ever able to walk a route that crossed eachof these bridges exactly once. The Swiss mathematician Leonhard Euler learnedof this frustrating phenomenon, and in 1736 he wrote an article [98] about work on the K onigsberg Bridge problem is considered by many to be thebeginning of the field of Graph The bridges in K Harris et al.,Combinatorics and Graph Theory , DOI: ,c Springer Science+Business Media, LLC 200821. Graph TheoryAt first, the usefulness of Euler s ideas and of Graph Theory itself was foundonly in solving puzzles and in analyzing games and other recreations.

2 In the mid1800s, however, people began to realize that graphs could beused to model manythings that were of interest in society. For instance, the Four Color Map Conjec-ture, introduced by DeMorgan in 1852, was a famous problem that was seem-ingly unrelated to Graph Theory . The conjecture stated thatfour is the maximumnumber of colors required to color any map where bordering regions are coloreddifferently. This conjecture can easily be phrased in termsof Graph Theory , andmany researchers used this approach during the dozen decades that the problemremained field of Graph Theory began to blossom in the twentieth century as moreand more modeling possibilities were recognized and the growth continues. Itis interesting to note that as specific applications have increased in number and inscope, the Theory itself has developed beautifully as Chapter 1 we investigate some of the major concepts and applications ofgraph Theory . Keep your eyes open for the K onigsberg BridgeProblem and theFour Color problem , for we will encounter them along the Introductory ConceptsA definition is the enclosing a wilderness of idea within a wall ofwords.

3 Samuel Butler, Graphs and Their RelativesAgraphconsists of two finite sets,VandE. Each element ofVis called avertex(pluralvertices). The elements ofE, callededges, are unordered pairs of instance, the setVmight be{a, b, c, d, e, f, g, h}, andEmight be{{a, d},{a, e},{b, c},{b, e},{b, g},{c, f},{d, f},{d, g},{g, h}}. Together,VandEare a have natural visual representations. Look at the diagram in Figure that each element ofVis represented by a small circle and that each ele-ment ofEis represented by a line drawn between the corresponding A visual representation of the Introductory Concepts3As a matter of fact, we can just as easily define a Graph to be a diagram consist-ing of small circles, called vertices, and curves, called edges, where each curveconnects two of the circles together. When we speak of a graphin this chapter, wewill almost always refer to such a can obtain similar structures by altering our definition in various ways.

4 Hereare some By replacing our setEwith a set oforderedpairs of vertices, we obtainadirected Graph , ordigraph(Figure ). Each edge of a digraph has aspecific A If we allow repeated elements in our set of edges, technically replacing oursetEwith a multiset, we obtain amultigraph(Figure ).FIGURE A By allowing edges to connect a vertex to itself ( loops ),we obtain apseu-dograph(Figure ).FIGURE A Graph Theory4. Allowing our edges to be arbitrary subsets of vertices (rather than just pairs)gives ushypergraphs(Figure ).e1e5e4e3e2 FIGURE A hypergraph with 7 vertices and 5 By allowingVorEto be an infinite set, we obtaininfinite graphs. Infinitegraphs are studied in Chapter this chapter we will focus on finite, simple graphs: those without loops ormultiple Ten people are seated around a circular table. Each personshakes handswith everyone at the table except the person sitting directly across the a Graph that models this Six fraternity brothers (Adam, Bert, Chuck, Doug, Ernie,and Filthy Frank)need to pair off as roommates for the upcoming school year.

5 Each personhas compiled a list of the people with whom he would be willingto share s list: DougBert s list: Adam, ErnieChuck s list: Doug, ErnieDoug s list: ChuckErnie s list: ErnieFrank s list: Adam, BertDraw a digraph that models this There are twelve women s basketball teams in the AtlanticCoast Confer-ence: Boston College (B), Clemson (C), Duke (D), Florida State (F), Geor-gia Tech (G), Miami (I), NC State (S), Univ. of Maryland (M), Univ. ofNorth Carolina (N), Univ. of Virginia (V), Virginia Tech (T), and WakeForest Univ. (W). At a certain point in midseason,B has played I, T*, WC has played D*, Introductory Concepts5D has played C*, S, WF has played N*, VG has played C, MI has played B, M, TS has played D, V*M has played G, I, NN has played F*, M, WV has played F, S*T has played B*, IW has played B, D, NThe asterisk(*) indicates that these teams have played eachother a multigraph that models this Can you explain why no resident of K onigsberg was ever able to walk aroute that crossed each bridge exactly once?

6 (We will encounter this ques-tion again in Section ) The BasicsYour first discipline is your vocabulary; Robert FrostIn this section we will introduce a number of basic Graph Theory terms andconcepts. Study them carefully and pay special attention tothe examples that areprovided. Our work together in the sections that follow willbe enriched by a solidunderstanding of these Very BasicsThe vertex set of a graphGis denoted byV(G), and the edge set is denotedbyE(G). We may refer to these sets simply asVandEif the context makes theparticular Graph clear. For notational convenience, instead of representing an edgeas{u, v}, we denote this simply byuv. Theorderof a graphGis the cardinalityof its vertex set, and thesizeof a Graph is the cardinality of its edge two verticesuandv, ifuv E, thenuandvare said to beadjacent. Inthis case,uandvare said to be theend verticesof the edgeuv. Ifuv6 E, thenuandvarenonadjacent. Furthermore, if an edgeehas a vertexvas an end vertex,we say (oropen neighborhood) of a vertexv, denoted byN(v), isthe set of vertices adjacent tov:N(v) ={x V|vx E}.

7 61. Graph TheoryTheclosed neighborhoodof a vertexv, denoted byN[v], is simply the set{v} N(v). Given a setSof vertices, we define the neighborhood ofS, denoted byN(S), to be the union of the neighborhoods of the vertices inS. Similarly, theclosed neighborhood ofS, denotedN[S], is defined to beS N(S).Thedegreeofv, denoted bydeg(v), is the number of edges incident withv. Insimple graphs, this is the same as the cardinality of the (open) neighborhood degreeof a graphG, denoted by (G), is defined to be (G) = max{deg(v)|v V(G)}.Similarly, theminimum degreeof a graphG, denoted by (G), is defined to be (G) = min{deg(v)|v V(G)}.Thedegree sequenceof a Graph of ordernis then-term sequence (usually writtenin descending order) of the vertex s use the graphGin Figure to illustrate some of these concepts:Ghas order 8 and size 9; verticesaandeare adjacent while verticesaandbarenonadjacent;N(d) ={a, f, g},N[d] ={a, d, f, g}; (G) = 3, (G) = 1; andthe degree sequence is3,3,3,2,2,2,2, following theorem is often referred to as the First Theorem of Graph a graphG, the sum of the degrees of the vertices is equal totwice the number of edges.

8 Consequently, the number of vertices with odd degreeis Vdeg(v). Notice that in countingS, we count each edgeexactly twice. Thus,S= 2|E|(the sum of the degrees is twice the number ofedges). SinceSis even, it must be that the number of vertices with odd and ConnectivityAwalkin a Graph is a sequence of (not necessarily distinct) verticesv1, v2, .. , vksuch thatvivi+1 Efori= 1,2, .. , k 1. Such a walk is sometimes calledav1 vkwalk, andv1andvkare theend verticesof the walk. If the vertices in awalk are distinct, then the walk is called apath. If the edges in a walk are distinct,then the walk is called atrail. In this way, every path is a trail, but not every trailis a path. Got it?Aclosed path, orcycle, is a pathv1, .. , vk(wherek 3) together with theedgevkv1. Similarly, a trail that begins and ends at the same vertex iscalled aclosed trail, orcircuit. Thelengthof a walk (or path, or trail, or cycle, or circuit)is its number of edges, counting again, let s illustrate these definitions with an example.

9 In the Graph ofFigure ,a,c,f,c,b,dis a walk of length 5. The sequenceb,a,c,b,drepresentsa trail of length 4, and the sequenced,g,b,a,c,f,erepresents a path of length Introductory Concepts7eafcdgbFIGURE ,g,d,b,c,a,b,gis a circuit, whilee,d,b,a,c,f,eis a cycle. In general, itis possible for a walk, trail, or path to have length 0, but theleast possible lengthof a circuit or cycle is following theorem is often referred to as the Second Theorem in this a graphGwith verticesuandv, everyu vwalk contains au au vwalk inG. We prove this theorem by induction on thelength ofW. IfWis of length 1 or 2, then it is easy to see thatWmust be a the induction hypothesis, suppose the result is true forall walks of length lessthank, and supposeWhas lengthk. Say thatWisu=w0, w1, w2, .. , wk 1, wk=vwhere the vertices are not necessarily distinct. If the vertices are in fact distinct,thenWitself is the desiredu vpath. If not, then letjbe the smallest integer suchthatwj=wrfor somer > j.

10 LetW1be the walku=w0, .. , wj, wr+1, .. , wk= walk has length strictly less thank, and therefore the induction hypothesisimplies thatW1contains au vpath. This means thatWcontains au vpath, andthe proof is now introduce two different operations on graphs:vertex deletionandedgedeletion. Given a graphGand a vertexv V(G), we letG vdenote the graphobtained by removingvand all edges incident withvfromG. IfSis a set ofvertices, we letG Sdenote the Graph obtained by removing each vertex ofSand all associated incident edges. Ifeis an edge ofG, thenG eis the graphobtained by removing only the edgee(its end vertices stay). IfTis a set of edges,thenG Tis the Graph obtained by deleting each edge ofTfromG. Figure examples of these Graph isconnectedif every pair of vertices can be joined by a path. Infor-mally, if one can pick up an entire Graph by grabbing just one vertex, then the81. Graph TheoryG - { eg, fg}G - dG - { f, g}G - cdaGgefdcbFIGURE Deletion Connected and disconnected is connected.