14. Some Graph Theory
<![if !supportEmptyParas]><![endif]>
1. Definitions andPerfect Graphs
<![if !supportEmptyParas]><![endif]>
We will investigate some of thebasics of graph theory in this section.
<![if !supportEmptyParas]><![endif]>
A graph G is a collection, E, of distinctunordered pairs of distinct elements of a set V. The elements of V arecalled vertices or nodes, and the pairs in E are called edges or arcsor the graph. (If a pair (w,v) can occur several times in E we call thestructure a multigraph. If edges like (v,v), which are called loops, areallowed, it is called a graph with loops.)
<![if !supportEmptyParas]><![endif]>
Graphs are things that underlie many mathematicalstructures, and in fact anything that involves pairs of elements, and thisincludes any kind of relationship between pairs of individuals.
<![if !supportEmptyParas]><![endif]>
A path in a graph from vertex v1to vertex vk, is a sequence of edges such that the first onecontains v1, and the last one contains vk, and eachconsecutive pair in the sequence has a vertex in common. The lengthof the path is the number of edges in it.
<![if !supportEmptyParas]><![endif]>
Thus (v, w), (w, j), (j,z), (z,q) is a path, and one of length 4 from vto q.
<![if !supportEmptyParas]><![endif]>
A graph is said to be connectedif for any two vertices in V there is a path from one to the other.
<![if !supportEmptyParas]><![endif]>
A subgraph of a graph Ghaving vertex set V and edge set E is a graph H having edge set contained in Vand edge set contained in E.
<![if !supportEmptyParas]><![endif]>
If the edge set of H consists of alledges of G both of whose endpoints lie in G, then H is said to be an inducedsubgraph of G.
<![if !supportEmptyParas]><![endif]>
Thus, the edge (v,w) and verticesv, w and j form a subgraph of the path described above. It is not an inducedsubgraph, since the edge (w,j) is an edge of path between vertices in thissubgraph which is not an edge of the subgraph.
<![if !supportEmptyParas]><![endif]>
A partition of a set iscollection of its subsets (calledblocks) no pair of which overlap, such that the union of all the blocks is thewhole set.
<![if !supportEmptyParas]><![endif]>
A partition of a graph G isa partition of both its edges E and itsvertices V into subsets {Vj}and {Ej} such that Gj = [Vj,Ej]is a graph.
<![if !supportEmptyParas]><![endif]>
Any graph can be partitioned into itsmaximal connected subgraphs, which are called its connectedcomponents. (This is only possible when there are no edges that go betweenthe subgraphs, since otherwise these edges will be lost in the partitioning,not being in any of the subgraphs. We can of course, if we want to, definepartitions of the edges set of a graph, and let the vertex sets of theresulting graphs overlap.)
<![if !supportEmptyParas]><![endif]>
A cycle in a graph is a paththat starts at the same vertex at which it ends. A chord of a cycle isan edge among its vertices that is not part of the cycle.
<![if !supportEmptyParas]><![endif]>
There is a standard notation forseveral kinds of graphs that are of general interest. The graph Ckis a k length cycle, consisting of k vertices and k edges that form acycles.
<![if !supportEmptyParas]><![endif]>
Kn is the symbolfor a complete graph with n vertices, which is one having all (C(n,2)(which is n(n-1)/2) edges.
<![if !supportEmptyParas]><![endif]>
A graph that can be partitionedinto k subsets, such that all edges have at most one member in each subset issaid to be k-partite, or k-colorable. Thus a bipartite or twocolorable graph is one whose vertex setV can be split into two parts, and all edges contain one vertex from each part.
<![if !supportEmptyParas]><![endif]>
Kn,m is the notation we use for a complete bipartite graph betweenvertex sets of size n and m. Thus it consists of all edges with one vertexamong the m and the other among the n, and no edges within each of these twosets.
<![if !supportEmptyParas]><![endif]>
A simple basic question is: underwhat circ*mstance is a graph bipartite, (that is, two-colorable)?
<![if !supportEmptyParas]><![endif]>
We can give an ‘excludedconfiguration’ condition for bipartness or two colorability.
<![if !supportEmptyParas]><![endif]>
A graph will be two colorable ifit has no odd length cycle.
If a graph has an odd lengthcycle, then it cannot be two colorable.
<![if !supportEmptyParas]><![endif]>
Suppose G has a cycle. If you start at a vertex v of colorone of the cycle, if the graph were two colored then v’s neighbors includingits neighbor, w, on its right in the cycle would have to have the other color,w’s neighbor on the right must have the first color and so on around the cycle.When you get back to where you start, v would have to have the opposite colorthan it had at first when the cycle has odd length, and this is a contradiction.
<![if !supportEmptyParas]><![endif]>
We can use a similar argument to prove that any graph thathas no odd length cycle is bipartite. We get a coloring instead of acontradiction by coloring neighbors oppositely to oneself.
<![if !supportEmptyParas]><![endif]>
We can start anywhere by coloring one vertex v one color,v’s neighbors the other, their neighbors the first color, their neighbors thesecond color, and so on until every vertex that can be reached by a path from vis colored.
<![if !supportEmptyParas]><![endif]>
The absence of odd cycles means that each vertex reachedwill have the same color every time it is colored.
<![if !supportEmptyParas]><![endif]>
In a similar vein, it is notpossible to color the complete graph, Kn, in fewer than n colors.In any coloring in fewer colors, two vertices must have the same color, butthey will be in an edge, and this violates the condition on coloring that alledges contain vertices of different colors.
<![if !supportEmptyParas]><![endif]>
The minimum number of colors neededto color the vertices of a graph G so that none of its edges have only onecolor is called the coloring number of G.
<![if !supportEmptyParas]><![endif]>
A complete graph is often called a clique.The size of the largest clique that can be made up of edges and vertices of Gis called the clique number of G.
<![if !supportEmptyParas]><![endif]>
The last statement before these definitions can thenbe phrased as: the coloring number of a graph is at least its clique number.
<![if !supportEmptyParas]><![endif]>
On the other hand, the coloring number of a graphG can be strictly greater than its clique number, as we have already seenfor C2j+1 when j is 2 or more. Such a graph has clique number 2(which means it contains no triangle) but coloring number 3.
<![if !supportEmptyParas]><![endif]>
If the coloring number and clique number are the samefor every induced subgraph of G, we call G a perfect graph.
<![if !supportEmptyParas]><![endif]>
The complement of a graph G is the graph on the samevertex set V, whose edges are precisely those that are not in the edge set ofG.
Thus the edge set of G and of its complement include allthe edges of the complete graph on V; and the edges of G and its complement donot overlap at all.
<![if !supportEmptyParas]><![endif]>
A famous result of graph theory is “The Perfect GraphTheorem” which reads:
<![if !supportEmptyParas]><![endif]>
A graph is perfect if and only if its complementis perfect.
<![if !supportEmptyParas]><![endif]>
By the way, the coloring number and clique number ofthe complement of G are parameters of interest by themselves.
<![if !supportEmptyParas]><![endif]>
The complement of G has all possible edges not in G.Thus a clique in the complement of G is a set of vertices among which thereare no edges of G,
<![if !supportEmptyParas]><![endif]>
We call this an independent set of G, a setof vertices unrelated by any edge of G.
The number of vertices in the largest possibleindependent set of G is called the independence number of G.
<![if !supportEmptyParas]><![endif]>
Thus the clique number of the complement of G isthe independence number of G.
<![if !supportEmptyParas]><![endif]>
In these terms we can describe the coloringnumber of G as the smallest number k such that we can partition the vertices ofG into k independent sets.
<![if !supportEmptyParas]><![endif]>
Similarly, the coloring number of the complementof G is the smallest number k’ so that we can partition the vertices of G intok’ cliques.
<![if !supportEmptyParas]><![endif]>
And theperfect graph theorem states that if for any induced subgraph H of G we can partition the vertices of H into anumber of cliques given by the size of H’s largest independent set, we can partition G (or any of its induced subgraphs) in into a number of independentsets given by the size of its largest clique.
<![if !supportEmptyParas]><![endif]>
As we have already noted one way, it is impossibleto partition the vertices of G into fewer of whatever. In any partition of V into cliques, sinceeach vertex of an independent I set must end up in a clique that contains noother member of I, the total number of blocks of the partition must be at leastthe maximum size of any I. And the same remark holds with the words clique andindependent set reversed.
<![if !supportEmptyParas]><![endif]>
Notice that perfection and this theorem require inthe premise that you can partition the vertices of any induced subgraph of Ginto a number of cliques given by the independence number of that subgraph. Thestatement of the perfect graph theorem would be false if you were to apply thecondition to G alone and not to its induced subgraphs.
<![if !supportEmptyParas]><![endif]>
We can see that by considering the graph Q, on 6vertices, that can be described as a 5-cycle with another edge linking thesixth vertex to one vertex of the cycle.
<![if !supportEmptyParas]><![endif]>
For this graph the independence number is 3 and itcan be partitioned into three cliques. On the other hand the clique number is 2and it cannot be partitioned into two independent sets.
<![if !supportEmptyParas]><![endif]>
However, the induced subgraph on the five verticesthat form the cycle has independence number 2 and clique number 2 and can onlybe partitioned into 3 cliques and 3 independent sets. Thus, neither Q nor itscomplement are perfect.
<![if !supportEmptyParas]><![endif]>
Another way to state the perfect graph theorem is:If you cannot partition the vertices of G into a number of cliques given by thesize of its largest independent set, then G has an induced subgraph H thatcannot be partitioned into a number of independent sets given by H’s cliquenumber.
<![if !supportEmptyParas]><![endif]>
14.2 Nice Graphs
<![if !supportEmptyParas]><![endif]>
Here isstill another way to describe this theorem.
<![if !supportEmptyParas]><![endif]>
We define a nice graph as follows:
<![if !supportEmptyParas]><![endif]>
A graph G is nice if given any maximum sizeclique C whose size (or cardinality) is |C|, we can assign integers 1 to |C| tothe vertices in C and can extend that assignment to all the vertices in V sothat the vertices assigned the letter j form an independent set for each j.
<![if !supportEmptyParas]><![endif]>
This is really the statement that G is nice whenits clique number and coloring number are the same.
<![if !supportEmptyParas]><![endif]>
A graph is c nice if its complement is nice,which means that its independence number and the smallest number of cliquesthat its vertices can be partitioned into are the same..
<![if !supportEmptyParas]><![endif]>
A graph is very nice if both G and itscomplement are nice (equivalently, G is both nice and c nice.)
<![if !supportEmptyParas]><![endif]>
In this terminology, the graph Q defined above (a5-cycle with another vertex linked to one vertex of the cycle) is c nice, butnot nice, and so not very nice.
<![if !supportEmptyParas]><![endif]>
Notice that if G is very nice when we can assign anordered pair (j,k) to each of its vertices such that those vertices with thesame first component form an independent set and those with the same secondcomponent form a clique, and the number of first components is |C|, the size ofthe largest clique, and the number of second components is the size of thelargest independent set.
<![if !supportEmptyParas]><![endif]>
A minimally not nice graph is a graph that isnot nice, but all its induced subgraphs are nice.
<![if !supportEmptyParas]><![endif]>
The perfect graph theorem in these terms is thestatement.
<![if !supportEmptyParas]><![endif]>
Every minimal not very nice graph is not nice atall (neither it nor its complement is nice.)
<![if !supportEmptyParas]><![endif]>
There is a stronger statement that has been aconjecture for about 40 years but has just recently been proven. As a matter offact by a remarkable coincidence, thereis a lecture this very afternoon by Paul Seymour, at 4:15 in 2-105 (goodrefreshments at 3:30 in 2-349) in which this result will be announced anddescribed
<![if !supportEmptyParas]><![endif]>
The statement is, the only minimally not verynice graphs are odd cycles of length 5 or more without chords, or thecomplements of these.
<![if !supportEmptyParas]><![endif]>
Since you can easily prove that these graphs are notnice at all, the Perfect Graph Theorem is an immediate consequence of it, andit is (or will be) called The Strong Perfect Graph Theorem.
<![if !supportEmptyParas]><![endif]>
And by the strong perfect graph theorem, a graphwill be very nice unless it or its complement contains a chordless odd cycle.
<![if !supportEmptyParas]><![endif]>
By the way very nice graphs, which include perfectgraphs, have some occasionally useful properties. One is as follows.
<![if !supportEmptyParas]><![endif]>
The cardinality of the vertex set of a very nicegraph G is at most the product of its clique number and its independencenumber.
This statement follows immediately from these twofacts
<![if !supportEmptyParas]><![endif]>
1. Each vertex can beassigned two numbers (a,b) with the first index having a number of possibleentries given by the clique number of G and the second by the independencenumber of G, with the indices representing which clique and independent setthey belong in partitions into cliques and independent sets.
<![if !supportEmptyParas]><![endif]>
2. No two vertices can have the same assigned pair; if they form anedge of G they cannot be in the same independent set, and if the do not form anedge, they cannot be in the same clique.
<![if !supportEmptyParas]><![endif]>
The same idea used in this last result can be applied toan arbitrary set of N distinct pointsin the plane, each described by coordinates (a,b).
<![if !supportEmptyParas]><![endif]>
We can ask, what can we say about the size (|I|or|D|) of the largest monotone increasing or decreasing subset of these N points?
<![if !supportEmptyParas]><![endif]>
We can define a graph whose edges are the pairssuch that the line between them has non-negative slope.
<![if !supportEmptyParas]><![endif]>
A monotone increasing set will be a clique in thisgraph, and a decreasing one will be an independent set.
<![if !supportEmptyParas]><![endif]>
We can conclude that N is at most |I||D|.
<![if !supportEmptyParas]><![endif]>
To get this result (using the strong perfect graphtheorem) we need only show that thegraph here defined can contain no chordless odd cycle. (The same result willhold by symmetry for its complement.)
<![if !supportEmptyParas]><![endif]>
Notice that two consecutive edges whose coordinatesboth increase or both decrease on the two length path they form will form twosides of a triangle. This means a chordless cycle must zig zag here, which isimpossible if it has odd length of 5 or more: there must be two consecutivezigs or zags and therefore a chord.
<![if !supportEmptyParas]><![endif]>
By the way,a common application of this statement is:
<![if !supportEmptyParas]><![endif]>
A permutation of N integers contains either anincreasing or decreasing sub permutation of length at least N1/2.
<![if !supportEmptyParas]><![endif]>
<![if !supportEmptyParas]><![endif]>
<![if !supportEmptyParas]><![endif]>
<![if !supportEmptyParas]><![endif]>
14.3Planarity of Graphs
<![if !supportEmptyParas]><![endif]>
A graph so far is an abstract thing, a creation ofyour mind. It consists of a set of vertices and of edges.
<![if !supportEmptyParas]><![endif]>
We define the degree of a vertex to be thenumber of edges that contain it as an endpoint.
<![if !supportEmptyParas]><![endif]>
We can, given a graph, attempt to draw it on a pieceof paper, representing its vertices by points and its edges by either straightlines, or nice curves.
<![if !supportEmptyParas]><![endif]>
We then define a graph G to be planar, if itcan be so drawn without any of the curves or lines representing its edgescrossing one another or meeting any other vertex on its way from one vertex tothe other.
<![if !supportEmptyParas]><![endif]>
The firstobvious question is: is there a convenient way to characterize planargraphs?
<![if !supportEmptyParas]><![endif]>
And there is.
<![if !supportEmptyParas]><![endif]>
Before discussing and proving it we make someremarks, which we will prove
<![if !supportEmptyParas]><![endif]>
<![if !supportLists]>1. <![endif]>Thereare two fairly small graphs that are not planar, K5 and K3,3.
<![if !supportLists]>2. <![endif]>Wecan add vertices in the middle of any of the edges of these two graphs as welike and that will not help to make them planar. (Adding a vertex in the middleof an edge here means replacing an edge (a,b) by two new edges (a,c) and (c,b))
<![if !supportLists]>3. <![endif]>Wecan split a vertex apart in the following way, and that also will not help tomake a graph planar. Take a vertex v that lies in edges a,b c ..z; replace itby 2 vertices, v1 and v2, so that each edge containing vcontains one of these, and there is an additional edge containing v1and v2. Doing so will not make a non-planar graph planar.
<![if !supportLists]>4. <![endif]>Everygraph which contains either K5 or K3,3 or something obtained from these by addingvertices in the middle edges or splitting vertices as noted in any way to themcannot be planar.
<![if !supportEmptyParas]><![endif]>
And the characterization is:
<![if !supportEmptyParas]><![endif]>
A graph is planar if it does not contain asubgraph obtainable by adding vertices to or splitting vertices in K5 or K3,3 any number of times. This result is calledKuratowski’s Theorem.
<![if !supportEmptyParas]><![endif]>
We will now prove all these statements.
<![if !supportEmptyParas]><![endif]>
The first follows from this remark
<![if !supportEmptyParas]><![endif]>
If we take two drawing of either K5(or more generally K2j+1) or K3,3 (more generally K2k+1,2j+1)in the plane (with no edge passing through any vertex not one of itsendpoints), the number of crossings between edges whose vertex sets aredisjoint has the same value mod 2 in each drawing (we count a point oftangency between two edges as either 2 or 0 crossings).
<![if !supportEmptyParas]><![endif]>
It follows immediately from this statement that ifwe can find a drawing of either K5 or K3, 3 with an oddnumber of crossings, it cannot be drawn with no crossings.
<![if !supportEmptyParas]><![endif]>
<![if !supportEmptyParas]><![endif]>
<![if !supportEmptyParas]><![endif]>
So let us prove the statement.
<![if !supportEmptyParas]><![endif]>
We start with two drawingsof the same graph, with vertex sets the same for each. We will take each edgeof the first one at a time and move it slowly and continuously until it reachesthe position of the same edge in the second drawing.
<![if !supportEmptyParas]><![endif]>
When we are done the twodrawings will have the same number of crossings between edges with disjointendpoints, since they will become identical.
<![if !supportEmptyParas]><![endif]>
To prove the result wenotice that the number of such crossings of the moved edge with any other edgehaving different endpoints can never change, mod 2.
<![if !supportEmptyParas]><![endif]>
How could it change? If theedge m being moved does not either become tangent to another edge q or cross over one of the endpoints of q, thenumber of crossings between m and q will not change in any way. The crossingsif any will merely slide along q.
<![if !supportEmptyParas]><![endif]>
When m and q become tangentand then cross, or become tangent and uncross, the number of crossings betweenm and q will change by 2 which is not at all mod 2.
<![if !supportEmptyParas]><![endif]>
When m crosses over anendpoint, v, of q then the number of crossing between m and q will change by 1.v has even degree in K2j+1 and odd degree in K2j+1,2k+1.
When m crosses over v, thenumber of crossings of m with every edge containing v as an endpoint willchange by 1, either up or down.
<![if !supportEmptyParas]><![endif]>
In the case of K2j+1,two of these crossings will involve edges which share endpoints with the twoends of m. The number of crossings not including these will therefore change byan even number when m passes over v, which is 0 mod 2.
<![if !supportEmptyParas]><![endif]>
In the case of K2j+1,2k+1,when m crosses over v, exactly one of the edges coming out of v will share anendpoint with m, so that again the number of crossings between edges whichdon’t share endpoints will change by 0 mod 2 upon m crossing over v.
<![if !supportEmptyParas]><![endif]>
We conclude that the numberof crossings in either case mod 2 can never change as the first drawing turnsinto the second one. So they must have been the same to begin with, which iswhat we set out to prove.
<![if !supportEmptyParas]><![endif]>
We prove the third remark by noticing that if a graph hasa split vertex v and is planar we can deform its drawing so as to make the edgebetween v1 and v2 shorter and shorter, until it entirelydisappears, without introducing any crossing of edges. In the process we undothe vertex splitting
<![if !supportEmptyParas]><![endif]>
The second and fourth remarks do not require proof, so weturn to the proof of Kuratowski’s Theorem, which says that the absence ofthese two configurations or their subdivisions and vertex splittings assubgraphs, which as we have seen ruin planarity, is enough to ensure planarity.
<![if !supportEmptyParas]><![endif]>
Suppose G is a graph that has no subgraph that is obtainablefrom K5 or K3,3 by adding or splitting vertices. Andsuppose G is the smallest such graph that perhaps cannot be drawn in the planewithout edge crossings.
<![if !supportEmptyParas]><![endif]>
Our proof uses the following outline.
<![if !supportEmptyParas]><![endif]>
We first find a cycle C in G such that there are edges or vertices which cannot be linked by apath that does not pass through at least one vertex of C.
If there is no such cyclethen we can show that C is planar without much difficulty.
<![if !supportEmptyParas]><![endif]>
The rest of the graph can then be divided into severalbridges. A bridge is a set of edges or vertices and edges that that can belinked by paths of G not meeting C.
<![if !supportEmptyParas]><![endif]>
The simplest kind of bridgeis a chord of the cycle.
<![if !supportEmptyParas]><![endif]>
We know by induction thatthe graph obtained from G by omitting any one bridge is planar, since G is aminimum graph whose planarity is in doubt.
<![if !supportEmptyParas]><![endif]>
We next define a bridge graph. Its vertices are thebridges, and there is an edge containing any pair of bridges that cannot bothbe drawn inside the cycle without a crossing.
<![if !supportEmptyParas]><![endif]>
For example, if the verticesof the cycle are, in order around the cycle , 1, 2 , 3, …, then (1,4) and (2,5)are examples of chordal bridges which cannot both be drawn on the same side ofthe cycle without a crossing. These then form an edge of the bridge graph.
<![if !supportEmptyParas]><![endif]>
If the bridge graph isbipartite, we can draw one part of it inside the cycle without crossings andthe other outside it without crossings, and G is then planar.
<![if !supportEmptyParas]><![endif]>
Thus, we will only getnon-planarity if the bridge graph is not bipartite. But that means it hasan odd cycle.
<![if !supportEmptyParas]><![endif]>
We can then show that any odd cycle in the bridge graphrequires a configuration in G that is obtained by vertex splitting or edgesubdivision from K5 or by edge subdivision of K3,3.
<![if !supportEmptyParas]><![endif]>
Suppose for example the bridge graph contains atriangle each bridge of which is a chord. The ends of the chords will then forma K3,3.
<![if !vml]>
<![endif]>
The only way that you will remember how to find a K5or a K3,3 here is if youfind them yourself. Hence:
Exercise:1. Draw picturesfor three cycles in the bridge graph with more complicated bridges that do notcontain paths as illustrated, and for five and seven cycles of chords that showhow to unsplit vertices (squeeze together vertices linked by an edge) toproduce a K5.
2. Draw K5 andK3,3 in the plane with onecrossing in each, thus completing the proof that they are not planar.
