14 Some Graph Theory Editor s Note These notes are quite dense and pack a lot of material in If you have trouble following them you may wish to reread the section or consult an outside source 14 1 Introductory Definitions We will investigate some of the basics of graph theory in this section A graph G is a collection of vertices and edges connecting some or all of these vertices More formally a graph is a collection E of distinct unordered pairs of distinct elements of a set V The elements of V are called vertices or nodes and the pairs in E are called edges or arcs or the graph If a pair w v can occur several times in E we call the structure a multigraph If edges like v v which are called loops are allowed it is called a graph with loops Graphs are things that underlie many mathematical structures and in fact anything that involves pairs of elements which includes any kind of relationship between pairs of individuals In a graph a path from vertex v1 to vertex v2 is a sequence of edges such that the first edge contains v1 the last edge contains v2 and each consecutive pair in the sequence has a vertex in common The length of the path is the number of edges in it Thus v w w j j z z q is a path from v to q of length 4 Here is a planar representation of this graph A graph is said to be connected if for any two vertices in V there is a path from one to the other Graph 1 above is an example of a connected graph If w j was missing from 1 then it would no longer be connected Note that by this definition a single vertex is considered a connected graph Consider a graph G with a vertex set V and an edge set E A subgraph of G is a graph H with a vertex set contained in V and an edge set contained in E If the edge set of H consists of all edges of G whose endpoints are in the vertex set of H then H is said to be an induced subgraph of G Thus the edge v w and the vertices v w j form a subgraph of 1 It is not an induced subgraph since the edge w j is in 1 and although both its vertices are in the subgraph it is not an edge of the subgraph A partition of a set is a collection of disjoint subsets called blocks such that the union of all the blocks is the whole set One place partitions are used is in the study of Riemann integration as means for dividing up the real number line A partition of the interval 1 10 for example could be the intervals 1 2 2 3 9 10 A partition of a graph G is a partition of both its edges E and its vertices V into subsets Vj and Ej such that there exists a graph Gj with Vj as its vertex set and Ej as its edge set A graph can be partitioned into its maximal connected subgraphs which are called its connected components if there are no edges that go between the subgraphs since otherwise these edges will be lost in the partitioning 1 This definition derives from the fact that if a graph is not connected then it can be partitioned into subgraphs each of which is connected and none of which are connected to each other For example graph 1 has 1 connected component Graph 2 below has 3 connected components A cycle in a graph is a path that starts at the same vertex at which it ends A chord of a cycle is an edge among its vertices that is not part of the cycle In graph 3 below the edges a b b c c d d e e f form a cycle and the edge b d is a chord There is a standard notation for several kinds of graphs that are of general interest The graph Ck is a cycle of length k consisting of k vertices and k edges 1 We can of course if we want to define partitions of the edges set of a graph and let the vertex sets of the resulting graphs overlap A complete graph with n vertices written Kn is a graph with n vertices that n contains every possible edge The number of edges in Kn is the binomial coefficient 2 see the exercises for more info 14 2 Coloring Graphs One concept that is helpful for characterizing graphs is that of graph coloring What we do is assign colors to each of the vertices in a graph with the condition that no two vertices that share an edge can have the same color There are many ways to assign colors to a particular graph some of which require more colors than others Of course any graph that has at least one edge will require at least two colors and many will require more The minimum number of colors required to color a graph is called the coloring number of the graph A graph that can be colored with at least k colors is said to be kcolorable A graph whose vertices can be partitioned into k subsets such that no vertices that share an edge are in the same subset is said to be k partite Thus a bipartite graph is one whose vertex set V can be split into two parts and all edges contain one vertex from each part Here is an example of a 5 partite graph with each of the 5 subsets colored to make them easier to distinguish We can see from the coloring of graph 4 above that it is 5 colorable in addition to being 5 partite In fact from the definition of a k partite graph we can see that any k partite graph will be k colorable see the exercises for more info Kn m is the notation we use for a complete bipartite graph between vertex sets of size n and m Thus it consists of two sets of vertices one of size m and one of size n and all possible edges with one vertex in set m the other in set n and no edges within each of these two sets Here is an example of a K3 2 graph A basic question is under what circumstances is a graph bipartite that is twocolorable We can give the following necessary and sufficient condition for bipartness or two colorability A graph will be two colorable if it has no odd length cycles If a graph has an odd length cycle then it cannot be two colorable We will prove the second part first Let G be a 2 colorable graph Suppose in order to reach a contradiction that G has an odd length cycle We will try to color the cycle one vertex at a time We start at vertex v1 and give it color …