14. Some Graph Theory

**1. Definitions and
Perfect Graphs**

We will investigate some of the basics of graph theory in this section.

A graph G 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 t**he 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, and this includes any kind of relationship between pairs of individuals.

A **path in a graph from vertex v _{1}
to vertex v_{k}, is a sequence of edges such that the first one
contains v_{1}, and the last one contains v_{k}, and each
consecutive pair in the sequence has a vertex in common**.

Thus (v, w), (w, j), (j,z), (z,q) is a path, and one of length 4 from v to q.

A graph is said to be **connected**
if for **any two vertices in V there is a path from one to the other.**

A **subgraph **of a graph G
having vertex set V and edge set E is a graph H having edge set contained in V
and edge set contained in E.

If the edge set of H consists of **all**
edges of G both of whose endpoints lie in G, then H is said to be an **induced
subgraph** of G.

Thus, the edge (v,w) and vertices v, w and j form a subgraph of the path described above. It is not an induced subgraph, since the edge (w,j) is an edge of path between vertices in this subgraph which is not an edge of the subgraph.

A **partition of a set** is
collection of its subsets (called
blocks) no pair of which overlap, such that the union of all the blocks is the
whole set.

A **partition of a graph G** is
a partition of both its edges E and its
vertices V into subsets {V_{j}}
and {E_{j}} such that G_{j} = [V_{j},E_{j}]
is a graph.

Any graph can be **partitioned into** **its
maximal** **connected subgraphs**, which are called its **connected
components**. (This is only possible when there are no edges that go between
the 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, define
partitions of the edges set of a graph, and let the vertex sets of the
resulting graphs overlap.)

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.

There is a standard notation for
several kinds of graphs that are of general interest. **The graph C _{k}
is a k length cycle**, consisting of k vertices and k edges that form a
cycles.

**K _{n}** is the symbol
for a

**A graph that can be partitioned
into k subsets, such that all edges have at most one member in each subset is
said to be k-partite, or k-colorable**. Thus a bipartite or two
colorable graph is one whose vertex set
V can be split into two parts, and all edges contain one vertex from each part.

**K _{n,m }^{ } **is the notation we use for

A simple basic question is: **under
what circumstance is a graph bipartite**, (that is, two-colorable)?

We can give an **‘excluded
configuration’** condition for bipartness or two colorability.

**A graph will be two colorable if
it has no odd length cycle.**

**If a graph has an odd length
cycle, then it cannot be two colorable**.

Suppose G has a cycle. If you start at a vertex v of color one of the cycle, if the graph were two colored then v’s neighbors including its 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 color than it had at first when the cycle has odd length, and this is a contradiction.

We can use a similar argument to prove that any graph that has no odd length cycle is bipartite. We get a coloring instead of a contradiction by coloring neighbors oppositely to oneself.

We can start anywhere by coloring one vertex v one color, v’s neighbors the other, their neighbors the first color, their neighbors the second color, and so on until every vertex that can be reached by a path from v is colored.

The absence of odd cycles means that each vertex reached will have the same color every time it is colored.

In a similar vein, **it is not
possible to color the complete graph, K _{n}, in fewer than n colors**.
In any coloring in fewer colors, two vertices must have the same color, but
they will be in an edge, and this violates the condition on coloring that all
edges contain vertices of different colors.

The minimum number of colors needed
to color the vertices of a graph G so that none of its edges have only one
color is called the **coloring number of G**.

A complete graph is often called **a clique**.
The size of the largest clique that can be made up of edges and vertices of G
is called **the clique number of G**.

The last statement before these definitions can then
be phrased as: **the coloring number of a graph is at least its clique number.
**

On the other hand, **the coloring number of a graph
G can be strictly greater than its clique number**, as we have already seen
for C_{2j+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 the **coloring number and clique number are the same
for every induced subgraph of G, we call G a** **perfect graph**.

The **complement of a graph G is the graph on the same
vertex set V, whose edges are precisely those that are not in the edge set of
G.**

Thus the edge set of G and of its complement include all the edges of the complete graph on V; and the edges of G and its complement do not overlap at all.

A famous result of graph theory is “**The Perfect Graph
Theorem**” which reads:

**A graph is perfect if and only if its complement
is perfect**.

By the way, the coloring number and clique number of the complement of G are parameters of interest by themselves.

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 there
are no edges of G,**

We call this an **independent se**t of G, a set
of vertices unrelated by any edge of G.

**The number of vertices in the largest possible
independent set of G is called the independence number of G.**

**Thus the clique number of the complement of G is
the independence number of G.**

** **

In these terms we can describe the **coloring
number of G as the smallest number k such that we can partition the vertices of
G into k independent sets**.

Similarly, **the coloring number of the complement
of G is the smallest number k’ so that we can partition the vertices of G into
k’ cliques**.

And the
perfect graph theorem states that **if for any induced subgraph H of G** **we can partition the vertices of H into a
number 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 independent
sets given by the size of its largest clique.**

** **

As we have already noted one way, it is impossible to partition the vertices of G into fewer of whatever. In any partition of V into cliques, since each vertex of an independent I set must end up in a clique that contains no other member of I, the total number of blocks of the partition must be at least the maximum size of any I. And the same remark holds with the words clique and independent set reversed.

Notice that perfection and this theorem require in the premise that you can partition the vertices of any induced subgraph of G into a number of cliques given by the independence number of that subgraph. The statement of the perfect graph theorem would be false if you were to apply the condition to G alone and not to its induced subgraphs.

We can see that by considering the graph Q, on 6 vertices, that can be described as a 5-cycle with another edge linking the sixth vertex to one vertex of the cycle.

For this graph the independence number is 3 and it can be partitioned into three cliques. On the other hand the clique number is 2 and it cannot be partitioned into two independent sets.

However, the induced subgraph on the five vertices that form the cycle has independence number 2 and clique number 2 and can only be partitioned into 3 cliques and 3 independent sets. Thus, neither Q nor its complement are perfect.

Another way to state the perfect graph theorem is: If you cannot partition the vertices of G into a number of cliques given by the size of its largest independent set, then G has an induced subgraph H that cannot be partitioned into a number of independent sets given by H’s clique number.

**14.2 Nice Graphs**

Here is still another way to describe this theorem.

We define a **nice graph** as follows:

**A graph G is nice** if given any maximum size
clique C whose size (or cardinality) is |C|, we can assign integers 1 to |C| to
the vertices in C and can extend that assignment to all the vertices in V so
that the vertices assigned the letter j form an independent set for each j.

**This is really the statement that G is nice when
its clique number and coloring number are the same**.

A graph **is c nic**e if its complement is nice,
which means that its independence number and the smallest number of cliques
that its vertices can be partitioned into are the same..

A graph is **very nice** if both **G and its
complement are nice** (equivalently, G is both nice and c nice.)

In this terminology, the graph Q defined above (a 5-cycle with another vertex linked to one vertex of the cycle) is c nice, but not nice, and so not very nice.

Notice that if G is very nice when we can assign an ordered pair (j,k) to each of its vertices such that those vertices with the same first component form an independent set and those with the same second component form a clique, and the number of first components is |C|, the size of the largest clique, and the number of second components is the size of the largest independent set.

**A minimally not nice graph** is a graph that is
not nice, but all its induced subgraphs are nice.

The perfect graph theorem in these terms is the statement.

**Every minimal not very nice graph is not nice at
all** (neither it nor its complement is nice.)

There is a stronger statement that has been a conjecture for about 40 years but has just recently been proven. As a matter of fact by a remarkable coincidence, there is a lecture this very afternoon by Paul Seymour, at 4:15 in 2-105 (good refreshments at 3:30 in 2-349) in which this result will be announced and described

The statement is, **the only minimally not very
nice graphs are odd cycles of length 5 or more without chords, or the
complements of these.**

Since you can easily prove that these graphs are not
nice at all, the Perfect Graph Theorem is an immediate consequence of it, and
it is (or will be) called **The Strong Perfect Graph Theorem.**

** **

**And by the strong perfect graph theorem, a graph
will be very nice unless it or its complement contains a chordless odd cycle.**

By the way very nice graphs, which include perfect graphs, have some occasionally useful properties. One is as follows.

** **

**The cardinality of the vertex set of a very nice
graph G is at most the product of its clique number and its independence
number.**

This statement follows immediately from these two facts

1. Each vertex can be assigned two numbers (a,b) with the first index having a number of possible entries given by the clique number of G and the second by the independence number of G, with the indices representing which clique and independent set they belong in partitions into cliques and independent sets.

2. No two vertices can have the same assigned pair; if they form an edge of G they cannot be in the same independent set, and if the do not form an edge, they cannot be in the same clique.

The same idea used in this last result can be applied to an arbitrary set of N distinct points in the plane, each described by coordinates (a,b).

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?**

**We can define a graph whose edges are the pairs
such that the line between them has non-negative slope. **

A monotone increasing set will be a clique in this graph, and a decreasing one will be an independent set.

**We can conclude that N is at most |I||D|. **

** **

To get this result (using the strong perfect graph theorem) we need only show that the graph here defined can contain no chordless odd cycle. (The same result will hold by symmetry for its complement.)

Notice that two consecutive edges whose coordinates both increase or both decrease on the two length path they form will form two sides of a triangle. This means a chordless cycle must zig zag here, which is impossible if it has odd length of 5 or more: there must be two consecutive zigs or zags and therefore a chord.

By the way, a common application of this statement is:

**A permutation of N integers contains either an
increasing or decreasing sub permutation of length at least N ^{1/2}.**

**14.3
Planarity of Graphs**

** **

A graph so far is an abstract thing, a creation of your mind. It consists of a set of vertices and of edges.

We define **the degree of a vertex** to **be the
number of edges that contain it as an endpoint.**

** **

We can, given a graph, attempt to draw it on a piece of paper, representing its vertices by points and its edges by either straight lines, or nice curves.

We then define a **graph G to be planar,** if **it
can be so drawn without any of the curves or lines representing its edges
crossing one another or meeting any other vertex on its way from one vertex to
the other.**

The first
obvious question is: **is there a convenient way to characterize planar
graphs? **

And there is.

Before discussing and proving it we make some remarks, which we will prove

1. There
are two fairly small graphs that are not planar, K_{5} and K_{3,3}.

2. We can add vertices in the middle of any of the edges of these two graphs as we like and that will not help to make them planar. (Adding a vertex in the middle of an edge here means replacing an edge (a,b) by two new edges (a,c) and (c,b))

3. We
can split a vertex apart in the following way, and that also will not help to
make a graph planar. Take a vertex v that lies in edges a,b c ..z; replace it
by 2 vertices, v_{1} and v_{2}, so that each edge containing v
contains one of these, and there is an additional edge containing v_{1}
and v_{2}. Doing so will not make a non-planar graph planar.

4. Every
graph which contains either K_{5} or K_{3,3} or something obtained from these by adding
vertices in the middle edges or splitting vertices as noted in any way to them
cannot be planar.

And the characterization is:

**A graph is planar if it does not contain a
subgraph obtainable by adding vertices to or splitting vertices in K _{5} or K_{3,3 } any number of times. This result is called
Kuratowski’s Theorem.**

We will now prove all these statements.

The first follows from this remark

**If we take two drawing of either K _{5}
(or more generally K_{2j+1}) or K_{3,3} (more generally K_{2k+1,2j+1})
in the plane (with no edge passing through any vertex not one of its
endpoints), the number of crossings between edges whose vertex sets are
disjoint has the same value mod 2 in each drawing (we count a point of
tangency between two edges as either 2 or 0 crossings).**

It follows immediately from this statement that if
we can find a drawing of either K_{5} or K_{3, 3} with an odd
number of crossings, it cannot be drawn with no crossings.

So let us prove the statement.

We start with two drawings of the same graph, with vertex sets the same for each. We will take each edge of the first one at a time and move it slowly and continuously until it reaches the position of the same edge in the second drawing.

When we are done the two drawings will have the same number of crossings between edges with disjoint endpoints, since they will become identical.

To prove the result we notice that the number of such crossings of the moved edge with any other edge having different endpoints can never change, mod 2.

How could it change? If the edge m being moved does not either become tangent to another edge q or cross over one of the endpoints of q, the number of crossings between m and q will not change in any way. The crossings if any will merely slide along q.

When m and q become tangent and then cross, or become tangent and uncross, the number of crossings between m and q will change by 2 which is not at all mod 2.

When m crosses over an
endpoint, v, of q then the number of crossing between m and q will change by 1.
v has even degree in K_{2j+1} and odd degree in K_{2j+1,2k+1}.

When m crosses over v, the number of crossings of m with every edge containing v as an endpoint will change by 1, either up or down.

In the case of K_{2j+1},
two of these crossings will involve edges which share endpoints with the two
ends of m. The number of crossings not including these will therefore change by
an even number when m passes over v, which is 0 mod 2.

In the case of K_{2j+1,2k+1},
when m crosses over v, exactly one of the edges coming out of v will share an
endpoint with m, so that again the number of crossings between edges which
don’t share endpoints will change by 0 mod 2 upon m crossing over v.

We conclude that the number of crossings in either case mod 2 can never change as the first drawing turns into the second one. So they must have been the same to begin with, which is what we set out to prove.

We prove the third remark by noticing that if a graph has
a split vertex v and is planar we can deform its drawing so as to make the edge
between v_{1} and v_{2 }shorter and shorter, until it entirely
disappears, without introducing any crossing of edges. In the process we undo
the vertex splitting

The second and fourth remarks do not require proof, so we
turn to the proof of Kuratowski’s Theorem, which says that **the absence of
these two configurations or their subdivisions and vertex splittings as
subgraphs, which as we have seen ruin planarity, is enough to ensure planarity.**

Suppose G is a graph that has no subgraph that is obtainable
from K_{5} or K_{3,3 }^{ }by adding or splitting vertices. And
suppose G is the smallest such graph that perhaps cannot be drawn in the plane
without edge crossings.

Our proof uses the following outline.

We first find a cycle C in G such that there are edges or vertices which cannot be linked by a path that does not pass through at least one vertex of C.

If there is no such cycle then we can show that C is planar without much difficulty.

The rest of the graph can then be divided into several bridges. A bridge is a set of edges or vertices and edges that that can be linked by paths of G not meeting C.

The simplest kind of bridge is a chord of the cycle.

We know by induction that the graph obtained from G by omitting any one bridge is planar, since G is a minimum graph whose planarity is in doubt.

We next define a bridge graph. Its vertices are the bridges, and there is an edge containing any pair of bridges that cannot both be drawn inside the cycle without a crossing.

For example, if the vertices of 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 of the cycle without a crossing. These then form an edge of the bridge graph.

If the bridge graph is bipartite, we can draw one part of it inside the cycle without crossings and the other outside it without crossings, and G is then planar.

Thus, **we will only get
non-planarity if the bridge graph is not bipartite**. But that means it has
an odd cycle.

We can then show that any odd cycle in the bridge graph
requires a configuration in G that is obtained by vertex splitting or edge
subdivision from K_{5} or by edge subdivision of K_{3,3.}

_{ }

_{ }Suppose for example the bridge graph contains a
triangle each bridge of which is a chord. The ends of the chords will then form
a K_{3,3}.

** **The only way that you will remember how to find a K_{5}
or a K_{3,3 } here is if you
find them yourself. Hence:

**Exercise:1. Draw pictures
for three cycles in the bridge graph with more complicated bridges that do not
contain paths as illustrated, and for five and seven cycles of chords that show
how to unsplit vertices (squeeze together vertices linked by an edge) to
produce a K _{5}.**

**2. Draw K _{5} and
K_{3,3 } in the plane with one
crossing in each, thus completing the proof that they are not planar.**