You can contact Stephen C. Locke at LockeS@acc.fau.edu.
[These pages are always being modified - Hit the RELOAD button to check for
an updated version. This never did quite catch up with what we were doing in
class (Spring 1996), nor was everything in here covered in class. I will keep
adding sporadically to these notes. More, now that I'm scheduled to teach an
undergraduate course in Graph Theory (Spring 1996).]
Florida Atlantic University is about to begin a
fund-raising campaign. The College of Science goal will be $10,000,000 over the
next five years. Large donations ($1,000,000) could endow a named chair.
$300,000 could endow a visiting professorship. Smaller donations might provide
technical facilities, etc. Even $100 donations help.
If you know anyone
interested in helping FAU, please contact:
Dr. John Wiesenfeld, Dean,
Charles E. Schmidt College of Science,
Florida Atlantic University,
Boca Raton, Florida,
U.S.A. 33431
July 1998: Big news! The Schmidt
Family Foundation has donated $15,000,000 to the College of Science in memory of
Charles E. Schmidt. This money, plus a matching amount from the State of
Florida, will be used to construct a building for our new program in Medicine
(two years here, two years at University of Miami). Some of the money will also
be used to hire senior professors in medicine-related fields, and also to buy
and maintain equipment.
The College of Science has been renamed the Charles E. Schmidt College of Science. In 1991, Charles Schmidt
donated $10,000,000 to the College of Humanities, which is now called the Dorothy F. Schmidt College of Arts and Letters. For people
keeping a record, this brings the total FAU donations of the Schmidt Family
(including matching State dollars) to about $53,000,000.
If you have a graph theory page, let me
know and I will include a link to it from my page for links to other
people's files.
Please note also: I have received requests for assistance on problems that are
standard undergraduate exercises. The most I will do in these situations is
point out the exercise in a standard text (in case the writer doesn't realize
that it is a standard problem) or refer the writer to a chapter in a standard
textbook.
Very Brief History
The earliest paper on graph theory seems to
be by Leonhard Euler, Solutio problematis ad geometriam situs
pertinentis,Commetarii Academiae Scientiarum Imperialis Petropolitanae
8(1736), 128-140. Euler discusses whether or not it is possible to stroll
around Konigsberg (later called Kaliningrad) crossing each of its bridges across
the Pregel (later called the Pregolya) exactly once. Euler gave the conditions
which are necessary to permit such a stroll.
Thomas Pennyngton Kirkman
(1856) and William Rowan Hamilton (1856) studied trips which visited certain
sites exactly once.
Graph Theory was born to study problems of
this type. For much more on the history of graph theory, I suggest the book Graph
Theory 1736-1936, by N.L. Biggs, E.K. Lloyd and R.J. Wilson.
Example of a Graph
The World Wide Web is an example of a
(directed) graph. The files are the vertices. A link from one file to
another is a directed edge (or arc).
Why Did I Start This?
These pages were started as I taught a
graduate course in Graph Theory (Spring 1996). My favourite text, Bondy and
Murty, was out of print. My second
choice was also out of print. Of course, I always want to do things which
are slightly different than are covered in a textbook anyway.
Who could
resist using the web to pass along information? I am trying, for the most part,
to write these pages from memory. Some material was taken very directly from a
course that Herb Shank taught at Waterloo, c. 1974. Bruce Richter was going to
put those notes into a monograph for Herb, but that hasn't materialized. I've
listed the unsolved problems from Appendix IV of Bondy and
Murty.
I'm scheduled to teach an undergraduate course in Graph
Theory (Spring 1997), so I hope I will soon begin adding more to these
pages. I will probably use West as the course
text, although I hear that Chartrand and
Lesniak will soon have a new edition.
These pages are not intended
to replace the standard
texts in Graph Theory, rather to give a place on the web where some of the
basic definitions can be found. I doubt if they will ever be as complete as a
text can be. On the other hand, I am not constrained by an editor (just by the
lack of symbols in html -- and that will change one day), so I can include
almost anything. You won't find any graphics here. They take up too much space.
(But I might learn JAVA.)
Students in the (Spring 1996) course were
expected to take notes, draw pictures of graphs, read some of the standard texts, etc. Also,
I have not tried to attribute every result to the researcher who produced the
result - some standard texts do this and some don't. If I don't point out a
result as being mine, then it almost certainly isn't.
The last third of
the (Spring 1996) course was comprised of student presentations from the
literature.
I do think the web might eventually replace the idea of
textbooks. Direct linking to definitions and other theorems is more pleasant
than searching for page references. There is a Yahoo site just for
Mathematics courses. (You may have gotten here from there.)
Basic Definitions
A simple graph can be thought of as a
triple G=(V,E,I), where V and E are disjoint finite sets
and I is an incidence relation such that every element of E is
incident with exactly two distinct elements of V and no two elements of
E are incident to the same pair of elements of V. Obviously, these
requirements can be varied (and we get general graphs, hypergraphs, infinite
graphs, etc.). We call V the vertex set and E the edge
set of G.
The degree, d(v), of a
vertex v is the number of edges with which it is incident. Two vertices
are adjacent if they are incident to a common edge. The
set of neighbours, N(v), of a vertex v is the set of
vertices which are adjacent to v. The degree of a vertex is also the
cardinality of its neighbour set.
A walk is an
alternating sequence of vertices and edges, with each edge being incident to the
vertices immediately preceeding and succeeding it in the sequence. A trail is a walk with no repeated edges. A
path is a walk with no repeated vertices. A walk is closed if the
initial vertex is also the terminal vertex. A cycle is a
closed trail with at least one edge and with no repeated vertices except that
the initial vertex is the terminal vertex.
The
length of a walk is the number of edges in the sequence defining the
walk. Thus, the length of a path or cycle is also the number of edges in the
path or cycle. If u and v are vertices, the
distance from u to v, written d(u,v), is the minimum
length of any path from u to v. In an undirected graph, this is
obviously a metric. The eccentricity, e(u), of the vertex u
is the maximum value of d(u,v), where v is allowed to range over
all of the vertices of the graph. The radius of the graph G,
rad(G), is the minimum value of e(u), for any vertex u, and
the diameter, diam(G), is the corresponding maximum value. It
should be obvious that diam(G) <= 2rad(G).
For a set of
vertices X, we use G[X] to denote the induced
subgraph of G whose vertex set is X and whose edge set is the
subset of E(G) consisting of those edges with both ends in X. For
a set S of edges, we use G[S] to denote the edge induced subgraph of G whose edge set is
S and whose vertex set is the subset of V(G) consisting of those
vertices incident with any edge in S. If Y is a subset of
V(G), we write G-Y for the subgraph G[V(G)-Y]. A graph is complete, or a clique, if
every pair of vertices are adjacent. We write Km for the
complete graph on m vertices.
A non-null graph
is connected if, for every pair of vertices, there is a walk whose ends
are the given vertices. Let us write u~v if there is path from u
to v. Then ~ is an equivalence relation. The equivalence classes under ~
are the vertex sets of the connected components of G. A connected
graph is therefore a graph with exactly one connected component. A non-complete graph G is k-connected if for
every proper subset Y of V(G) with fewer than k elements,
G-Y is connected. A graph G has
connectivityk if G is k-connected but not
(k+1)-connected. A complete graph on k+1 vertices is defined to
have connectivityk. See Dirac's Theorem and Menger's Theorem.