Graph Theory Lecture Notes - Pennsylvania State University

1 Graph Theory : Penn State Math 485 LectureNotesVersion Griffin 2011-2021 Licensed under a Creative Commons Attribution-Noncommercial-Share Alike United States LicenseWith Contributions By:Elena KosyginaSuraj ShekharContentsList of FiguresvPrefacexiChapter 1. Introduction to Graph Theory11. An Overview of Graph Theory12. Graphs, Multi-Graphs, Simple Graphs23. Directed Graphs74. Elementary Graph Properties: Degrees and Degree Sequences95. Subgraphs146. Graph Complement, Cliques and Independent Sets15 Chapter 2. More Definitions and Theorems191. Paths, Walks, and Cycles192. More Graph Properties: Diameter, Radius, Circumference, Girth213. More on Trails and Cycles224.

2 Graph Components235. Introduction to Centrality286. Bipartite Graphs297. Acyclic Graphs and Trees31 Chapter 3. Trees, Algorithms and Matroids391. Two Tree Search Algorithms392. Prim s spanning Tree Algorithm413. Computational Complexity of Prim s Algorithm474. Kruskal s Algorithm495. Shortest Path Problem in a Positively Weighted Graph516. Floyd-Warshall Algorithm557. Greedy Algorithms and Matroids60 Chapter 4. Some Algebraic Graph Theory651. Isomorphism and Automorphism652. Fields and Matrices713. Special Matrices and Vectors734. Matrix Representations of Graphs735. Determinants, Eigenvalue and Eigenvectors766. Properties of the Eigenvalues of the Adjacency Matrix79 Chapter 5.

3 Applications of Algebraic Graph Theory83iii1. Basis ofRn832. Eigenvector Centrality853. Markov Chains and Random Walks884. Page Rank915. The Graph Laplacian95 Chapter 6. A Brief Introduction to Linear Programming1011. Linear Programming: Notation1012. Intuitive Solutions of Linear Programming Problems1023. Some Basic Facts about Linear Programming Problems1054. Solving Linear Programming Problems with a Computer1085. Karush-Kuhn-Tucker (KKT) Conditions1106. Duality113 Chapter 7. An Introduction to Network Flows and Combinatorial Optimization1191. The Maximum Flow Problem1192. The Dual of the Flow Maximization Problem1203. The Max-Flow / Min-Cut Theorem1224.

4 An algorithm for Finding Optimal Flow1255. Applications of the Max Flow / Min Cut Theorem1296. More Applications of the Max Flow / Min Cut Theorem131 Chapter 8. Coloring1371. Vertex Coloring of Graphs1372. Some Elementary Logic1393. NP-Completeness ofk-Coloring1414. Graph Sizes andk-Colorability145 Chapter 9. A Short Introduction to Random Graphs1471. Bernoulli Random Graphs1472. First Order Graph Language and 0 1 properties1503. Erd os-R enyi Random Graphs151 Chapter 10. Some More Algebraic Graph Theory1571. Vector Spaces and Linear Transformation1572. Linear Span and Basis1593. Vector Spaces of a Graph1604. Cycle Space1615. Cut Space1646.

5 The Relation of Cycle Space to Cut Space167 Bibliography169ivList of city of K onigsburg is built on a river and consists of four islands, whichcan be reached by means of seven bridges. The question Euler was interestedin answering is: Is it possible to go from island to island traversing eachbridge only once? (Picture courtesy of Wikipedia and Wikimedia Commons: ) is easier for explanation to represent a Graph by a diagram in which verticesare represented by points (or squares, circles, triangles etc.) and edges arerepresented by lines connecting self-loop is an edge in a graphGthat contains exactly one vertex. That is, anedge that is a one element subset of the vertex set.

6 Self-loops are illustrated byloops at the vertex in each island as a dot and each bridge as a line or curve connectingthe dots simplifies the visual representation of the seven K onigsburg World War II two of the seven original K onigsburg bridges weredestroyed. Later two more were made into modern highways (but they are stillbridges). Is it now possible to go from island to island traversing each bridgeonly once? (Picture courtesy of Wikipedia and Wikimedia Commons: ) multigraph is a Graph in which a pair of nodes can have more than one edgeconnecting them. When this occurs, the for a graphG= (V,E), the elementEis a collection ormultisetrather than a set. This is because there are duplicateelements (edges) in the (a) A directed Graph .

7 (b) A directed Graph with a self-loop. In a directed Graph ,edges are directed; that is they are ordered pairs of elements drawn from thevertex set. The ordering of the pair gives the direction of the Graph above has a degree sequenced= (4,3,2,2,1). These are the degreesof the vertices in the Graph arranged in increasing construct a new graphG fromGthat has a larger valuer(See ) than our original graphGdid. This contradicts our assumption thatGwaschosen to complete Graph , the Petersen Graph and the Dodecahedron. All Platonicsolids are three-dimensional representations of regular graphs, but not all regulargraphs are Platonic solids. These figures were generated with Petersen Graph is shown (a) with a sub- Graph highlighted (b) and thatsub- Graph displayed on its own (c).

8 A sub- Graph of a Graph is another graphwhose vertices and edges are sub-collections of those of the original subgraph (a) is induced by the vertex subsetV ={6,7,8,9,10}. Thesubgraph shown in (b) is a spanning sub- Graph and is induced by edge subsetE ={{1,6},{2,9},{3,7},{4,10},{5,8},{6,7},{ 6,10},{7,8},{8,9},{9,10}}. clique is a set of vertices in a Graph that induce a complete Graph as asubgraph and so that no larger set of vertices has this property. The Graph inthis figure has 3 Graph and its complement with cliques in one illustrated and independent setsin the other covering is a set of vertices so that ever edge has at least one endpoint insidethe covering walk (a), cycle (b), Eulerian trail (c) and Hamiltonian path (d) are illustrated.

9 Illustrate the 6-cycle and diameter of this Graph is 2, the radius is 1. It s girth is 3 and itscircumference is can create a new walk from an existing walk by removing closed sub-walksfrom the show how to decompose an (Eulerian) tour into an edge disjoint set of cycles,thus illustrating Theorem connected Graph (a), a disconnected Graph (b) and a connected digraph thatis not strongly connected (c). illustrate a vertex cut and a cut vertex (a singleton vertex cut) and an edgecut and a cut edge (a singleton edge cut). Cuts are sets of vertices or edgeswhose removal from a Graph creates a new Graph with more components thanthe original on a cycle, then we can repair pathwbygoing the long way around thecycleto reachvn+ with four Graph for which you will compute bipartite Graph has two classes of vertices and edges in the Graph only existsbetween elements of different of the main argument in the proof that a Graph is bipartite if andonly if all cycles have even tree is shown.

10 Imagining the tree upside down illustrates the tree like natureof the Graph Petersen Graph is shown on the left while a spanning tree is shown on theright in proof of 4 = 5 requires us to assume the existence of two paths in graphTconnecting vertexvto vertexv . This assumption implies the existence of acycle, contradicting our assumptions illustrate an Eulerian Graph and note that each vertex has even also show how to decompose this Eulerian Graph s edge set into the unionof edge-disjoint cycles, thus illustrating Theorem Following the tourconstruction procedure (starting at Vertex 5), will give the illustrated breadth first walk of a tree explores the tree in an ever widening depth first walk of a tree explores the tree in an ever deepening construction of a breadth first spanning tree is a straightforward way toconstruct a spanning tree of a Graph or check to see if its construction of a depth first spanning tree is a straightforward way toconstruct a spanning tree of a Graph or check to see if its connected.