CCS Discrete II Professor: Padraic Bartlett [605448]

CCS Discrete II Professor: Padraic Bartlett
Lecture 4: Graph Theory and the Four-Color Theorem
Week 4 UCSB 2015
Through the rest of this class, we're going to refer frequently to things called graphs !
If you haven't seen graphs before, we dene them here:
Denition. AgraphGwithnvertices and medges consists of the following two objects:
1. a setV=fv1;:::v ng, the members of which we call G'svertices , and
2. a setE=fe1;:::e mg, the members of which we call G'sedges , where each edge eiis
an unordered pair of distinct elements in V, and no unordered pair is repeated. For
a given edge e=fv;wg, we will often refer to the two vertices v;wcontained by eas
its endpoints.
Example. The following pair ( V;E) denes a graph Gon ve vertices and ve edges:
V=f1;2;3;4;5g,
E=ff1;2g;f2;3g;f3;4g;f4;5g;f5;1gg.
Something mathematicians like to do to quickly represent graphs is draw them, which we
can do by taking each vertex and assigning it a point in the plane, and taking each edge
and drawing a curve between the two vertices represented by that edge. For example, one
way to draw our graph Gis the following:
1
2
3 45
We could also draw our graph like this:
1
3
5 24
In general, all we care about for our graphs is their vertices and their edges; we don't
usually care about how they are drawn, so long as they consist of the same vertices connected
via the same edges. Also, we usually will not care about how we \label" the vertices of a
graph: i.e. we will usually skip the labelings on our graphs, and just draw them as vertices
connected by edges.
Some graphs get special names:
1

Denition. Thecycle graph onnvertices,Cn, is the graph on the vertex set fv1;v2;:::v ng
with edge set E(Cn) =ffv1;v2g;fv2;v3g;:::fvn1;vng;fvn;v1gg. The cycle graphs Cncan
be drawn as n-gons, as depicted below:
…
Denition. Thepath graph onnvertices,Pn, is the graph on the vertex set fv1;v2;:::v ng
with edge set E(Cn) =ffv1;v2g;fv2;v3g;:::fvn1;vngg. The path graphs Pncan be drawn
as paths of length n, as depicted below:
…
Denition. Thecomplete graph Kn.The complete graph on nvertices,Kn, is the
simple graph on the vertex set fv1;v2;:::v ngthat has every possible edge: in other words,
E(Kn) =ffvi;vjg:i6=jg. We draw several of these graphs below:
Every vertex in a Knhas degree n1, as it has an edge connecting it to each of the other
n1 vertices; as well, a Knhasn(n1)=2 edges in total in it, by the degree-sum formula.
(Explicitly: every vertex has degree n1 and there are nvertices, therefore the sum of the
degrees ofKn's vertices is n(n1). We've shown that this quantity is twice the number of
edges in the graph; dividing by 2 then tells us that the number of edges in Knisn(n1)=2,
as claimed.)
Denition. Thecomplete bipartite graph Kn;m.The complete bipartite graph on
n+mvertices with part sizes nandm,Kn;m, is the following graph:
V(Kn;m) =fv1;v2;:::v n;w1;w2;:::w mg.
E(Kn;m) consists of all of the edges between the n-part and the m-part; in other
words,E(Kn;m) =f(vi;wj) : 1in;1jmg.
The vertices viall have degree m, as they have precisely medges leaving them (one to every
vertexwj); similarly, the vertices wjall have degree n. By either the degree-sum formula
or just counting, we can see that there are nmedges inKn;m.
2

Denition. Given a graph Gand another graph H, we say that His asubgraph ofGif
and only if V(H)V(G) andE(H)E(G).
Denition. Given a graph G, we callGconnected if for any two vertices x;y2V(G),
there is a path that starts at xand ends at yin our graph G.
Denition. If a graphGhas no subgraphs that are cycle graphs, we call Gacyclic . A
treeTis a graph that's both connected and acyclic. In a tree, a leaf is a vertex whose
degree is 1.
Example. The following graph is a tree:
1 The Four-Color Theorem
Graph theory got its start in 1736, when Euler studied the Seven Bridges of K onigsberg
problem. However, I claim that it rst blossomed in earnest in 1852 when Guthrie came up
with the Four-Color Problem.
Theorem. Take any map, which for our purposes is a way to partition the plane R2into
a collection of connected regions R1;:::R nwith continuous boundaries. There is some way
to assign each region Rito a color in the set fR;G;B;Yg, such that if two regions Ri;Rj
are \touching" (i.e. they share some nonzero length of boundary between them,) then those
two regions must receive dierent colors.
We're going to prove this theorem in this class! First, some background:
Denition. Take any map M. We can turn this into a graph as follows:
Assign to each region Ria vertexvi.
Connectvitovjwith an edge if the regions Ri;Rjare touching.
We call this graph the dual graph toM.
We give an example here:
Example. Consider the following map:
3

This map consists of 14 regions. If you count, you can see that the gure drawn consists
thirteen triangles; as well, we have the \outer" region consisting of everything else left over,
which forms a very strange 15-gon.
Now, take each region, and assign to it a vertex. As well, connect two regions sharing a
border with an edge: this will give you the following graph, with edges given by the dashed
teal lines and vertices given by the yellow dots:
Note how we have drawn the edges so that they connect two adjacent countries by traveling
through the border that they share! This observation is useful to recall when thinking about
our second denition:
Denition. We say that a graph Gisplanar if we can draw it in the plane so that none
of its edges intersect.
Sometimes, it will help to think of planarity in the following way:
4

Denition. We call a connected graph Gplanar if we can draw it on the sphere S2in the
following fashion:
Each vertex of Gis represented by a point on the sphere.
Each edge in Gis represented by a continuous path drawn on the sphere connecting
the points corresponding to its vertices.
These paths do not intersect each other, except for the trivial situation where two
paths share a common endpoint.
We call such a drawing a planar embedding ofGon the sphere.
It is not hard to see that this denition is equivalent to our earlier denition of planarity.
Simply use the stereographic projection map (drawn below) to translate any graph on the
plane to a graph on the sphere:
By drawing lines from the \north pole" (0,0,1) through points either in the xy-plane or on the surface of
the sphere, we can translate graphs drawn on the sphere (in red) to graphs drawn in the plane (in yellow.)
Denition. For any connected planar graph G, we can dene a face ofGto be a connected
region of Rwhose boundary is given by the edges of G.
For example, the following graph has four faces, as labeled:
f1
f2 f4f3
Notice that we always have the \outside" face in these drawings, which can be easy to
forget about when drawing our graphs on the plane. This is one reason why I like to think
about these graphs as drawn on the sphere; in this setting, there is no \outside" face, as all
of the faces are equally natural to work with.
5

f1 f2 f3f4
f2f1 f3f4This observation has a nice accompanying lemma:
Lemma. Take any connected planar graph G, and any face FofG. ThenGcan be drawn
on the plane in such a way that Fis the outside face of G.
Proof. Take a planar embedding of Gon the unit sphere. Rotate this \drawn-upon" sphere
so that the face Fcontains the north pole (0 ;0;1) of the sphere. Now, perform stereographic
projection to create a planar embedding of GinR2. By construction, the face Fis now the
outside face, which proves our claim.
It bears noting that not all graphs are planar:
Proposition. The graph K5is not planar.
Proof. Draw a 5-cycle on the sphere. If the edges of this 5-cycle do not intersect each other,
then the resulting pentagon partitions the sphere into two parts, each part of which is
bounded by this pentagon. Take either one of these parts; notice that within that part, we
can draw at most two nonintersecting edges connecting nonadjacent vertices in that part.
Consequently, it is impossible to draw the additional 5 edges required to create K5without
using overlapping edges. Therefore it is impossible to nd a planar embedding of K5on the
sphere, as claimed!
For maps, something you may have noticed is the following:
Observation. The dual graph to any map Mis connected and planar.
Proof. On the homework!
The reason we care about this is that it gives us the following more graph-theoretic way
to describe the four-color theorem:
Theorem. Take any connected planar graph on nitely many vertices. There is a way to
assign each of its vertices one of the four colors fR;G;B;Ygsuch that no edge in this graph
has both endpoints colored the same color.
In general, this concept of coloring comes up all the time in graph theory! We give it a
name here:
6

Denition. A graphGis calledk-colorable if there is a collection of kdistinct colors that
we can map the vertices of Gto, so that no edge in Ghas both endpoints colored the same
color. Given a graph G, we dene the chromatic number ofG,(G), as the smallest
numberksuch thatGisk-colorable.
This gives us one last rephrasing of the four-color theorem:
Theorem. IfGis a connected planar graph on nitely many vertices, then (G)4.
. . . So. Before we can start Kempe's proof, we need one last bit of background, which is
the concept of Euler characteristic:
Theorem. (Euler characteristic.) Take any connected graph that has been drawn in R2as
a planar graph. Then, if Vis the number of vertices, Eis the number of edges, and Fis
the number of faces in this graph, we have the following relation:
VE+F= 2:
Proof. We will actually prove a stronger claim: we will show that any planar multigraph
(a graph, but where we allow multiple edges between vertices, and also edges that start and
end at the same vertex) satises the VE+F= 2 formula. For the rest of this proof, we
will assume that graph and multigraph are synonymous; once we are done with this proof,
though, we will stop assuming this.
31
2
4 56f1
f2
f3f6
f4f5
We proceed by induction on the number of vertices. Suppose that V= 1. Then our
graph looks like something of the following form:
…
…
…
7

I claim that VE+F= 2 for any of these graphs, and prove it by a second induction
on the number of edges. For a zero-edge graph, this is easy; we have one vertex, no edges
and one face, we have VE+F= 10 + 1 = 2. Now, assume via induction that every
one-vertex multigraph on nedges hasVE+F= 2. Take any graph on one vertex with
n+ 1 edges. Pick one of these edges, and look at it.
I claim that this edge borders exactly two faces. To see why, take any edge, and assign
an orientation to it (i.e. if our edge is fx;yg, then orient the edge so that we travel from
xtoy.) If you do this, then our edge has two \sides," the left- and right-hand sides, if we
travel along it via this orientation.
xy
(left) (right)
xy
(left) (right)
There are two possibilities, as drawn above: either the left- and right-hand sides are dierent,
or they are the same. This tells us that our edge either borders one or two faces! To see
that we have exactly two, we now recall that our edge (because our graph has exactly one
vertex) must start and end at the same vertex. In other words, it is a closed loop: i.e.
its outside is dierent from its inside! In other words, our left- and right-hand sides are
dierent, and our edge separates two distinct faces.
Therefore, deleting this edge does the following things to the graph: it decreases our
edge count by 1, and also decreases our face count by 1 (as we merge two faces when we
delete this edge.) In other words, deleting this edge does not change VE+F! But by
induction we know that VE+F= 2 for all 1-vertex graphs on nedges, which is what
we get if we delete this edge from a n+ 1-edge graph. So we're done!
This settles our base case for our larger induction on V, the number of vertices. We
now go to the second phase of an inductive proof: we show how to reduce larger cases to
smaller cases!
To do this, consider the following operation, called edge contraction . Take any edge
with two distinct endpoints. Delete this edge, and combine its two endpoints together: this
gives us a new graph! We draw examples of this process below: we start with a graph on
six vertices, and contract one by one the edges labeled in red at each step.
31
2
4 561
2
4 561
2
56
1
2 6 2 6 2
8

Contracting an edge decreases the number of vertices by 1 at each step, as it \squishes
together" two adjacent vertices into one vertex. It also decreases the number of edges by 1
at each step, as we are contracting an edge to a point! Finally, it never changes the number
of faces; if two faces were distinct before this process happens, they stay distinct, as we're
not making any cuts in any of our boundaries (and instead are just shrinking them partially
a bit!)
But this means that VE+Fis still constant! Therefore, by induction, if VE+Fholds
for everyn-vertex multigraph, it holds for any n+ 1-vertex multigraph by just contracting
an edge! This nishes our induction, and thus our proof.
Using this theorem, we can prove the following useful lemma, which is the only part of
the Euler characteristic property that we need for our graph:
Lemma. Take any connected planar graph G. Then there is some vertex vin our graph
with degree at most 5.
Proof. We proceed by contradiction. Assume that every vertex has at least degree 6; we
will create a contradiction to the claim that VE+F= 2.
First, consider the sumP
v2Gdeg(v). On one hand, this is twice the number of edges
inG: this is because each edge shows up twice in this sum (once for each endpoint vwhen
we're calculating deg( v).) On the other hand, if each vertex has degree at least 6, we have
X
v2Gdeg(v)X
v2G6 = 6V:
Consequently, we have 2 E6V, and therefore E=3V.
Similarly: notice that every face Fof our planar graph must have at least three edges
bounding it, because our faces are made out of edges in our graph. Also, if we sum over
all faces the number of edges in each face, we get again at most twice the number of edges;
this is because each edge is in at most two faces (as discussed earlier!) Therefore, we have
2EX
f2Gfacedeg(f)X
f2G3 = 3F;
and therefore that 2 E=3F.
Therefore, we have
2 =VE+FE=3E+ 2E=3 = 0;
which is clearly impossible. Therefore, we have a contradiction, and can conclude that our
initial assumption | that all vertices have degree at least 6 | is false!
2 Kempe's Proof
With this notation set up, Kempe's proof of the four-color theorem is actually fairly straight-
forward! We give it here.
9

Proof. We proceed by contradiction. Assume not: that there are connected planar graphs
on nitely many vertices that need at least 5 colors to be colored properly. Consequently,
there must be some smallest connected planar graph G, in terms of the number of its
vertices, that needs at least ve colors to color its vertices! Pick such a graph G. Notice
that if we remove any vertex vfromG, we have a graph on a smaller number of vertices
thanG. Consequently, the graph Gnfvgcanbe colored with four colors!
Letvbe the vertex in Gwith degree at most 5. Delete vfromG: this leaves us a graph
that we can four-color. Do so.
Our goal is now the following: to add vback in and (by possibly changing the coloring
ofGnfvg) givevone of our four colors, so that we have a four-coloring of G! This will
prove that our initial assumption | that a Gcan exist that needs ve colors | is false,
and therefore prove our theorem.
We proceed by cases, considering v's possible degrees.
1.vhas degree 1, 2 or 3. In these cases, note that when we add vback in, it is adjacent
to at most three colors! So there is some fourth color left over. Give vthat color.
v G-{v}
2.vhas degree 4. In this case, there are two possibilities:
In the four neighbors a;b;c;d ofv, some color is not used. In this case, we are
in the same kind of situation as above: just color vwith the color that doesn't
show up in its neighbors?
In the four neighbors a;b;c;d ofv, each color is used exactly once. So, up to the
names of the colors, we are in the following situation:
v ab
c
d
First, notice that without losing any generality we may assume that there are
edgesa$b$c$d$a. To see why, notice the following:
(a) Adding these edges does not change the assumed property that (G)5,
as extra edges only makes it \harder" for us to color a graph.
10

(b) We can always draw in these edges if they do not exist: for example, if the
edgefa;bgdid not exist, we could add it in without breaking planarity by
simply drawing a path that is \very close" to the two edges fa;vgandfv;bg.
This path will not cross other edges, as there are no other edges leaving v.
vb
c
da
(c) Therefore, because we have preserved (G)5 andG's planarity, we can
put these edges into Gwithout changing any of our arguments thus far!
By the argument above, we can now assume our graph looks like the following:
vb
c da
Now, do the following: for any two colors C1;C2, letGC1;C2denote the subgraph
ofGgiven by taking all of the vertices in Gthat are colored either C1orC2,
along with all of the edges that connect C1vertices toC2vertices.
Look at the red-yellow subgraph GRY. In this graph, there are two possibilities:
(a) There is no path from atocin this graph. In other words, dene ARYas
the subgraph of GRYgiven by taking all of the GRYvertices that have paths
toa, along with all of the edges in our graph between such vertices.
vb
c daARY
11

Suppose that we \switch" the colors red and yellow in the subgraph ARY.
Does it create any issues with our coloring?
Let's check. No edge between two vertices in ARYis broken (i.e. has both
endpoints made the same color) by this process; before it had one red and
one yellow endpoint, and now it has one yellow and one red endpoint. As
well, no edge that involves no vertices in ARYis broken by this process, as
we did not change the colors of either of their endpoints!
vb
c daARY
vb
c daAYR
Finally, consider any edge with one endpoint in ARYand another endpoint
not inARY. In order for this edge to have one endpoint in ARYand another
not inARY, one endpoint must be red or yellow (the endpoint in our set)
and the other must be green or blue (the endpoint not in our set!) So if we
switch red and yellow in ARY, this edge is also not broken!
No edges are broken by this swap; therefore we still have a valid coloring.
Furthermore, in this coloring, vhas no neighbors that are red; so we can
colorvred and have a four-coloring of our entire graph G!
(b) Alternately, (a) does not happen. In this case, there is a path from atoc
made entirely of red-yellow vertices linked by edges. In this case: look at
the graphGGB.
vb
c da
DGB
12

In particular, notice that there cannot be a path from btodalong green-blue
edges, because our graph is planar and any such path would have to cross
our red-yellow edges! Therefore, we can dene DGBto be the collection of
all of theGGBvertices that have paths to d, along with the edges in our
graph between such vertices. As noted above, d =2BGB.
Now, switch the colors GandBinDGB! This causes no con
icts, by exactly
the same argument as above, and yields a graph where vhas no green neigh-
bor; therefore, we can give vthe color green, and have a proper four-coloring
as desired.
vb
c da
DGB
vb
c da
DBG
3.vhas degree 5. Again, as before, we can assume that all four of the colors in our graph
occur onG's neighbors, because if they do not we can simply give vwhichever color
is missing. Again, as before, we can assume that the neighbors of vare connected by
the following pentagonal structure.:
vab
c
d ev ab
c
d e
This is because of the following:
Adding edges to our graph will never make it easier to color a graph: all they do
is give us more conditions on what vertices have to have dierent colors, which
only makes coloring harder .
Furthermore we can add these edges without breaking planarity by simply draw-
ing them arbitrarily close to the v-edges.
Up to symmetry and colorings, then, we are in the following situation:
13

v ab
c
d eThis is because we have to repeat one color (so it might as well be red,) we have to use
all of the other colors (so we have green, blue and yellow in some order,) red cannot
occur on two adjacent vertices (because there are edges between adjacent vertices,)
and therefore up to rotation and
ipping we have the above.
Do the following:
(a) First, look at the GGBsubgraph. Either the vertex bis not connected to din this
subgraph, in which case we can do the switching-trick that we discussed earlier.
Otherwise, bisconnected to dinGGB, and we have a green-blue chain from b
tod.
(b) Now, look at the GGYsubgraph. Similarly, either the vertex bis not connected to
ein this subgraph, in which case we can do the switching-trick that we discussed
earlier, or it is, and we have a green-yellow chain from btoe.
If we were able to switch in either of the two cases above, then vhas only three colors
amongst its neighbors, and we can color it with whatever color remains.
Otherwise, we are in the following case:
vab
c
d e
Do the following:
(a) First, look at the GRBsubgraph. Because of the green-yellow chain, the vertices
aanddare not connected to each other. Therefore, we can switch red and blue
in thea-connected part of this subgraph!
14

(b) Now, look at the GRYsubgraph. Because of the green-blue chain, the vertices c
andeare not connected to each other. Therefore, we can switch red and yellow
in thec-connected part of this subgraph!
vab
c
d evab
c
d e
This yields a graph where vhas no red neighbor: consequently, we can color vred,
which gives us a proper four-coloring! This proves our claim.
3 Plot Twist
This proof . . . is in fact Kempe's famous
awed proof of the four-color theorem, which stood
for 11+ years before being disproven! In particular, it was disproven : i.e. the proof you've
read above is false !
Guess what your HW is for today?
4 Graphs: Terminology
We transition from the four-color theorem to a more careful discussion of the denitions
and terms we need to discuss graphs. We start by discussing what it means for two graphs
to be the \same," in the same sense that we talked about groups or elds or vector spaces
or sets being the same: isomorphisms !
Which is to say the following: In our rst examples of graphs, we labeled all of our
vertices because this is part of the denition of what a graph *is* { a collection of labeled
vertices and edges between them.
However, when we had to actually do tricky mathematics | the four-color theorem |
we stopped labeling our graphs! And in general, I claim that we don't really care about the
labelings of most of our graphs. For example, consider the following pair of graphs:
15

These graphs are, in one sense, dierent; the rst graph has an edge connecting 1 to 2,
where the second graph does not. However, in another sense, these graphs are representing
the same situation: they're both depicting the graph sketched out by a pentagon!
For graphs like the ones in our menagerie, we don't care so much about the labeling of
the vertices; rather, the interesting features of these graphs are the intersections of their
edges and vertices. In other words, we want to say that both of the graphs below are
\the" Petersen graph1: even though they initially look rather dierent, there is a way of
\relabeling" the vertices on the second graph so that ( i;j) is an edge in the rst graph i
it's an edge in the relabeled second graph.
How can we do this? What notion can we introduce that will allow us to regard such
graphs as being the \same," in a well-dened sense? Well, consider the following:
Denition. We say that two graphs G1;G2areisomorphic if and only if there is a map
:V(G1)!V(G2) such that
matches each element of V(G1) to a unique element of V(G2), and vice-versa: in
other words, is a way of relabeling G1's vertices with G2's labels, and vice-versa.
 fvi;vjgis an edge in G1if and only iff(v1);(v2)gis an edge in G2.
We will often regard two isomorphic graphs as being the \same," and therefore refer
to graphs like Knor the Petersen graph without specifying or worrying about what the
vertices are labeled.
A concept that's much more interesting (given the idea of isomorphism) is the concept
of asubgraph , which we dene below:
1The Petersen graph PThe Petersen graph Pis a graph on ten vertices, drawn below:
The vertices in Pall have degree three; by counting or the degree-sum formula, Phas 15 edges. It is
notorious as being the counterexample or example to a number of conjectures in graph theory!
16

Denition. Given a graph Gand another graph H, we say that His asubgraph ofGif
and only if V(H)V(G) andE(H)E(G).
Example. The Petersen graph has the disjoint union of two pentagons C5tC5as a sub-
graph, which we shade in red below:
In general, when we ask if a graph His a subgraph of a graph G, we won't mention
a labeling of H's vertices; in this situation, we're actually asking whether there is *any*
subgraph of Gthat is isomorphic toH.
For example, one question we could ask is the following: what kinds of graphs contain
an triangle (i.e. a C3) as a subgraph? Or, more generally, what kinds of graphs contain an
odd cycle (i.e. a C2k+1) as a subgraph?
We answer this in the next section:
5 Classifying Bipartite Graphs
Denition. We call a graph Gbipartite if and only if we can break the set V(G) up into
two partsV1(G) andV2(G);such that every edge e2E(G) has one endpoint in V1(G) and
one endpoint in V2(G).
Alternately, we say that a graph is bipartite i there is some way to color G's vertices
red and blue { i.e. to take every vertex in Gand assign it either the color blue or color red,
but not both or neither { so that every edge has one blue endpoint and one red endpoint.
Example. The following graph is bipartite, with indicated partition ( V1;V2):
17

However, there are graphs that are not bipartite; for example, C3, the triangle, is not
bipartite! This is not very hard to see: in any partition of C3's vertices into two sets V1and
V2, one of the two sets V1orV2has to contain two vertices of our triangle. Therefore, there
is an edge in C3with both endpoints in one of our partitions; so this partition does not
makeC3bipartite. Because this holds for every possible partition, we can conclude that no
such partition exists { i.e. C3is not bipartite!
In general, we can say much more:
Proposition 1. C2k+1is not bipartite.
Proof. We will prove this proposition with a proof by contradiction. In other words, we will
assume that Cnis bipartite, and from there we'll deduce something we know to be false;
from there, we can conclude that our assumption must not have been true in the rst place
(as it led us to something false,) and therefore that Cnis not bipartite.
To do this: as stated, we'll suppose for contradiction that C2k+1is bipartite. Then,
there must be some way of coloring the vertices fv1;:::v 2k+1gofCnred and blue, so that
no edge is monochrome (i.e. has two red endpoints or two blue endpoints.)
How do we do this? Well: look at vk+1.vk+1has to be either red or blue: without any
loss of generality2, we can assume that it's red. Then, because no edge in C1is monochrome,
we specically know that none of vk+1's neighbors can be red: in other words, they both
have to be blue! So both vkandvk+2are blue.
Similarly, we know that neither of vkorvk+2's neighbors can be blue: so both vk1and
vk+3have to be red! Repeating this process, we can see that
vk+1being red forces
vk;vk+2to be blue, which forces
vk1;vk+3to be red, which forces
vk2;vk+4to be blue, which forces
. . .
which forces v1;v2k+1to both be the same color.
But there is an edge between v1andvninC2k+1! This contradicts the denition of bipartite:
therefore, we've reached a contradiction. Consequently, Cncannot be bipartite.
This allows us to actually classify a large number of graphs as not being bipartite:
Proposition 2. If a graphGhas a subgraph isomorphic to C2k+1, thenGis not bipartite.
2The phrase \without loss of generality" is something mathematicians are overly fond of. In general, it's
used in situations where there is some sort of symmetry to the situation that allows you to assume that a
certain situation holds: for example, in this use, we're assuming that v1is red because it has to be either
red or blue, and if it was blue we could just switch the colors \red" and \blue" through the entire proof.
18

Proof. Suppose that Gcontains a subgraph Hthat's not bipartite. Then, for any coloring
ofH's vertices, there is some edge in Hthat's monochrome. Therefore, because any coloring
ofG's vertices into two parts will also color H's vertices, we know that any coloring of G's
vertices with the colors red and blue will create a monochrome edge; therefore, Gcannot
be bipartite.
Is this it? Or are there other ways in which a graph can fail to be bipartite? Surprisingly,
as it turns out, there isn't:
Proposition 3. A graphGonnvertices is bipartite if and only if none of its subgraphs
are isomorphic to an odd cycle.
Proof. Our earlier proposition proved the \if" direction of this claim: i.e. if a graph is
bipartite, it doesn't have any odd cycles as subgraphs. We focus now on the \only if"
direction: i.e. given a graph that doesn't contain any odd cycles, we seek to show that it is
bipartite.
First, note the following denitions:
Denition. A graphGis called connected i for any two vertices v;w2V(G), there is
a path connecting vandw.
Denition. Given a graph G, divide it into subgraphs H1;:::H ksuch that each of the sub-
graphsHiare connected, and for any two Hi;Hj's there aren't any edges with one endpoint
inHiand one endpoint in Hj. These parts Hiare called the connected components of
G; a graphGis connected if it has only one connected component.
Denition. For a graph Gand two vertices v;wwe dene the distanced(v;w) between
vandwas the number of edges of the smallest path connecting vandw. For a connected
graph, this quantity is always dened, d(v;v) = 0, andd(v;w)>0 for anyv6=w.
Take our graph G, and divide it into its connected components H1;:::H k. If we can
nd a red-blue coloring of each connected component Hithat shows it's bipartite, we can
combine all of these colorings to get a coloring of all of G; because there are no edges between
the connected components, this combined coloring would show that Gitself is bipartite!
Therefore, it suces to just show that any connected graph Honnvertices without
any odd cycles in it is bipartite. To do this, take any vertex y2V(H), and construct the
following sets:
N0=fw:d(v;y) = 0g
N1=fw:d(v;y) = 1g
N2=fw:d(v;y) = 2g
. . .
Nn=fw:d(v;y) =ng
19

First, notice that every vertex vshows up in at least one of these sets, as His connected
and hasnvertices (and thus, any path in Hhas lengthn.) Furthermore, no vertex shows
up in more than one of these sets, because distance is well-dened. Finally, notice that for
anyx2Nkand any path Pgiven byy=v0e01v1e12:::e k1;kvk=x, each of the vertices vj
lies inNj. This is because each of these has a path of length jfromytovj(just take our
path and cut it o at vj), and has no shorter path (because if there was a shorter path, we
could use it to get from ytoxin less than ksteps, and therefore d(y;x) would not be k.)
Now, color all of the vertices in the even N-sets red, and all of the vertices in the odd
N-sets blue. We claim that there are no monochromatic edges.
To see this, take any edge fv1;v2gin our graph H. Letd(y;v 1) =kandd(y;v 2) =l,
P1be a path of length kconnecting v1withy, andP2be a path of length lconnecting
v2withy. These paths may intersect repeatedly, so take xto be the furthest-away vertex
fromythat's in both of these paths. Let P0
1be the path that we get by starting P1atx
and proceeding to v1, andP0
2be the path that we get by starting P2atxand proceeding
tov2.
There are two possiblities. Either xis one ofv1orv2, in which case (because there's
an edge from v1tov2) the distance from ytov1is either one greater or one less than the
distance from ytov2. In either case, v1andv2have dierent colors (because our colors
alternated between red and blue as our distance increased,) so this edge is not monochrome.
Otherwise, xis neitherv1orv2. In this case, look at the cycle formed by doing the
following:
Start atx, and proceed along P0
1.
Once we get to v1, travel along the edge fv1;v2g.
Now, go backwards along P0
2back tox.
This is a cycle, because P0
1andP0
2don't share any vertices in common apart from x. What
is its length? Well, the length of P0
1is justd(y;v 1)d(y;x), the length of P0
2is just
d(y;v 2)d(y;x), and the length of a single edge is just 1; so, the total length of this path
is
d(y;v 1)d(y;x) +d(y;v 2)d(y;x) + 1 =d(y;v 1) +d(y;v 2)(2d(y;x) + 1):
We know that this cannot be odd, because our graph has no odd cycles; so the number
above is even! Because (2 d(y;x) + 1) is odd, this means that d(y;v 1) +d(y;v 2) must also
20

be odd; in other words, exactly one of d(y;v 1);d(y;v 2) can be odd ,and exactly one can be
even. But this means specically that exactly one must be blue and one must be red (under
our coloring scheme,) so our edge must not be monochromatic.
Therefore, our graph has no monochromatic edges; so it's bipartite!
21