Graph theory Math 220-01, Spring 2014. Last modified: December 20, 2013.

Graph theory course blurb, from Explore page syllabus. However, the ``Blackboard page'' for the course, which also has this information, will further contain proprietary material open only to Georgetown students who are registered for it.


A graph is a set of nodes with some pairs connected
by links, as towns are joined by roads or people by
relationships. Basically, graphs are what you get
when you take a network and strip away the extra
numerical information such as vehicles/hr and cost.
Directed graphs include diagrams of syntax as well
as the URLs and hypertext pointers that make up the
World-Wide Web. The goal of the course is to give
students a good idea of what graphs are and how
they fit into mathematics and its applications.

This is a fun course about very useful mathematical
objects, which can be represented making simple
drawings on a piece of paper (or computer screen).
As the above (and following) remarks make clear,
graphs are now ubiquitous in many areas of science
and even of society, and their study has become
extremely popular.

I will also use a powerful software tool from
Wolfram Research (maker of the famous Wolfram Alpha)
in order to illustrate graphs. Georgetown has a
site license, and students who wish can take the
opportunity to learn how to use this software, which
is called "Mathematica" (version 9).

Students will be required to recognize some of the
basic properties of graphs and to compute various
graph-invariants, such as vertex-connectivity or
crossing number, after these concepts have been
introduced in class. Some simple proofs will also
be on the agenda but for the harder derivations, we
will mostly rely on plausibility arguments.

The course meets twice a week (T/Th 3:30 -- 4:45,
in Reiss 281). In addition to Mathematics, Computer
Science, and Statistics majors, for whom it should
be a required course, a variety of other fields,
including Sociology, Psychology, Biology, and Physics,
as well as Medicine, Business, Foreign Service, and
Law, have found graph theory valuable. 

The lecturer, Paul Kainen, has worked in both the
theory and applications of graphs and wrote his first 
paper on graphs when he was a graduate student, based
on work he did while still an undergraduate. It is
hoped that some of the students will be similarly
inspired to begin a research career, but all of you
will be able to use it as a tool in your professions.

Texts & Readings

We are using the classic text, Graph Theory, by
Frank Harary, Addison-Wesley, Reading, MA, 1969,
which is available on-line at

http://www.dtic.mil/dtic/tr/fulltext/u2/705364.pdf

but the book is so good that every math student
should buy a copy (used copies are available from
Amazon, and the book has been reprinted as well,
unfortunately at a quite high price). As a number
of important results have appeared in the last 4
decades, some remarks will illustrate what is new.

Assignments & Expectations of Students

Here is the approximate syllabus. We cover most of
chapters 1 to 12 of the book (approximately 150 pp),
together with a small amount of additional material
on more recent results and applications. Chapter 1
is introductory, Chapters 2--5 are on graphs, blocks,
trees, and connectivity, and deal with structure.
Chapters 6--10 cover partitions, traversability,
line graphs, factorization, and coverings of graphs,
while Chapter 11 is on planarity and Chapter 12 on
colorings of graphs, both of which are important in
applications. If time permits, we will also look
at Chapter 16, on directed graphs. A more detailed
syllabus including which sections we shall omit and
a list of homework problems will appear a few weeks
prior to the start of the class.

Homework will be assigned so that students can
"learn by doing" (as procedural knowledge is more
valuable than mere memorization of results). The
answers will be discussed in class and students
will have the opportunity to present and discuss
their own solutions to the problems. 

Course grade will depend on 2 midterms and a final
exam, as well as on a number of announced and
unannounced quizzes. Since the class period of
75 minutes is too long for a lecture, there will
usually be a quiz or a discussion to break it up.
Your quiz total will count as 20 percent, the two
midterms as 40 percent, and the final exam also
as 40 percent. With the instructor's permission,
students who have worked hard but haven't done well
on quizzes and/or midterms will be allowed to do a
project in order to show that they do have a useful
grasp of the subject. Projects are due April 28.

Midterm exams will be held in the evening from 7:30
until 9:30 in order to remove time pressure and to
save the class periods to cover the material. The
first midterm (on chapters 1--5) will be held on
Tuesday, Feb. 11, and the second midterm (on chap.
6--10) on Tuesday, March 25. Classes end on April
28, so our last class is on April 24. The final
exam will be cumulative and will be on whatever we
have covered in class. Final exam locations will
be available from the Registrar's Office, while the
locations of the two midterms will probably be St.
Mary's Hall (exact room information will be posted).

Graph theory has no formal prerequisites but you
should probably be comfortable with sets and basic
logic: E.g., the union of two sets is the set of
all elements which belong to either of them; if
A and B are statements, A implies B, and B is known
to be false, then A is also false. Those who are
uncertain about their qualifications to take the
class should make appointments to see me, so that
I can give you some guidance. 

See colorful outerplanar layouts for some circulant graphs for some of what one can do with graphs.

The course, Graph Theory, Math 220-01, will meet Tues. and Thurs. 3:30 to 4:45 pm in Reiss 284.

Office: 313.6 St. Mary's, phone 202-687-2703

e-mail: Kainen at Georgetown dot edu

My office hours in Spring 2014 will be T/Th/F 5 to 6:30 pm. Back to the index page .