How to contact me.
Why I don't want to talk about:
If you have a graph theory page, let me
know and I might include a link to it from
for links to other people's files. I won't usually link to commercial pages.
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
My favourite text,
Bondy and Murty,
was out of print.
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.
In Spring 1997, I used
as the course text (and that now has a second edition). I hear that
and Lesniak had a new edition.
These pages are not intended to replace the
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
site just for Mathematics courses.
(You may have gotten here from there.)
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, directed graphs, oriented 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,
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 distinct vertices is adjacent.
(The adjacency matrix of a complete graph has zeroes on the main diagonal, and ones off the diagonal.)
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
A non-complete graph G is k-connected if
for every proper subset Y of
V(G) with fewer than
G-Y is connected.
A graph G has
connectivity k if G
is k-connected but not (k+1)-connected.
A complete graph on k+1 vertices is defined to have
(of a graph embedded in on a surface)
Crosscap (of a non-orientable surface)
Handle (of an orientable surface)
This page can now be reached from
of Mathematical Sciences
Florida Atlantic University
777 Glades Road
Boca Raton, Florida 33431-0991
Office: Room 286, Science & Engineering
Phone: (561) 297-3350
Fax: (561) 297-2436
Last modified September 1, 2000, by S.C. Locke.