Students who require accommodations and who have documentation from
Disability Services (8742098)
should make arrangements with me as soon as possible.
New Room 
Washburn 208
Updated 12/12/04
We will use Introduction
to Graph Theory by Chartrand and Zhang as a text for this course. I
hope you find this to be a fine book with many examples, applications, and
exercises. Supplementary material will be used for those topics which are
not covered in our text.
Some of the topics that are
covered in this course are not in the text. For those topics, some
supplementary material will be used and you will be expected to take careful
notes in class. Downloads for all materials are listed here as they
become available. Even Cycles
Euler Circuits Planar (Kuratowski
and 5color) Brooks
and Vizings
A combinatorial
graph, or simply, graph, is a set of vertices V and edges E such
that each edge consists of an unordered pairs of vertices. We can picture
graphs using dots and curves. For each vertex, draw a dot, anywhere you
like. Represent the edge {u, v} by drawing a curve from one vertex
to the other. For example, we draw the graph G=(V, E), where V={a,
b, c, d, f, g} and E={{a, b}, {a, d}, {a, g}, {b, c}, {b, f}, {c, d},
{c, g}, {d, f}, {f, g}} below.
Notice that there is no vertex or dot in the
center of the drawing.
Graph theory has many applications in Electrical
Engineering and Computer Science. For example, the electrical engineer will be
interested in planar graphs and the computer scientist in algorithms to
properly color graphs. We will see some of these applications, but we must
build up some background knowledge about graphs before we can make sense of
such things as the thickness of a graph or the crossing number of a
graph.
In the course of our study of Graph Theory, we will
learn about the following topics as well: set theory, proof techniques,
enumeration, and recursive formulas. There is no official prerequisite for this
course however, it is recommended that you have been exposed to a variety of
math and science courses. All topics will be treated in an introductory manner.
Specifically, we will cover the following
topics:
Motivation:
Jobs and
applicants
Scheduling
4color
map problem
Computer
networks
Circuit
board design
Background:
subgraphs
walks,
trails, paths, circuits, cycles
connected
graph
digraphs
multigraphs
common
classes of graphs
matrix
representation
Degrees 
A party problem
Isomorphic
graphs  Algorithms
Coloring
vertices  Scheduling
Trees 
Counting labeled trees
Spanning
trees  Minimum weight
Prefix
codes
Connectivity
Eulerian
graphs
Hamiltonian
graphs  The Traveling Salesman Problem
Planar
graphs
Coloring
planar graphs
Coloring
edges of graphs
Matching
Factoring
Ramsey
numbers
Domination
Network
flows
Games
Theory and Games on graphs
Date 
Topic 
Sec 
Date 
Topic 
Sec 



Sep 9 
Motivation 
1.1 
Sep 14 
Background 
1.2, 1.3 
Sep 16 
Background 
1.4 
Sep 21 
Degrees 
2.1, 2.2 
Sep 23 
Degrees 
2.3, 2.4 
Sep 28 
Isomorphic graphs 
3.1 
Sep 30 
Coloring vertices 
10.2 
Oct 5 
Trees 
4.1, 4.2 
Oct 7 
Spanning trees 
4.3 
Oct 12 


Oct 14 
Exam 1 

Oct 19 
Connectivity 
5.1, 5.2 
Oct 21 
Connectivity 
5.3 
Oct 26 
Eulerian graphs 
6.1 
Oct 28 
Hamiltonian graphs 
6.2 



Nov 4 
Planar graphs 
9.1 
Nov 9 
Coloring planar graphs Project proposal due 
10.1 
Nov 10(Wed) 
Coloring edges 
10.3 
Nov 16 
Matching 
8.1 
Nov 18 
Factoring 
8.2 
Nov 23 
Project due 




Nov 30 


Dec 2 
Exam 2 

Dec 7 
Special topic 

Dec 9 
Extra Credit 




Dec 16 
Final Exam 

You learn by doing rather than by watching.
Therefore, homework is very important. You also learn by practice, so do
as many of the examples assigned as possible. Homework will be assigned each
time we begin to cover a new section in class. You should complete it by the
next class period. I will ask you to hand in selected problems every week or
so. You should provide careful explanations and be neat. When the exercise asks
for a proof, give a formal proof. We will practice this in class.
These problems will challenge your problem solving abilities. You may work in
groups provided you follow the following guidelines.
There are benefits to discussing the problems with your classmates. If
you become stuck on a problem, fresh ideas from someone else might provide you
with some new angles to try. In the academic community as well as in
business and industry, people often work in teams. So, it is good to get
some practice working with others. Working with someone from class will
help you to improve your math communication skills as well.
I encourage you to work together under the
following circumstances.
v
Begin the problem on your own, do as much as
you can.
v
Ask someone from the class to explain the
basic outline of a solution.
v
If working with someone else, sometimes they
will also ask you for your understanding of the basic outline.
v
Take what you learned and write out the
solution on your own, using your own words.
v
Never copy word for word from anyone else’s
paper. In fact it is better not to look at anyone else’s completed
written solution or to show yours to anyone else.
v If you still do not completely understand the solution, you
can ask your professor to look at what you wrote and try to clear up any parts
of the solution that are not completely clear and accurate.
The following is an excerpt from the University
Manual.
8.27.11 A student's name on any written exercise
(theme, report, notebook, paper, examination) shall be regarded as assurance
that the work is the result of the student's own thought and study, stated in
the student's own words and produced without assistance, except as quotation
marks, references and footnotes acknowledge the use of other sources of
assistance. Occasionally, students may be authorized to work jointly, but such
effort must be indicated as joint on the work submitted. Submitting the
same paper for more than one course is considered a breach of academic
integrity unless prior approval is given by the instructors.
Whenever you would like to discuss the class
material, have any questions or are stuck on the homework, please visit me in
my office either during my office hours or by appointment.
Hints or solutions to the odd numbered problems are given in the back of
the text. Be sure to try the problem before looking at the
solution. Give it at least 15 minutes!
SECTION 
HOMEWORK 
HAND IN 
Due date 
Assn # 
1.1 
3, 4, 6, 7b, 8, 10 
4, 6, 8, 10 
Sep 14 
1 
1.2 
11, 12, 15, 17 
15, 17(b) 
Sep 21 
2 
1.3 
21, 22, 24, 25, 27 
22, 24 
Sep 21 
2 
1.4 
30, 32(a,b) 



2.1 
1, 2, 3, 4, 5, 7, 9, 11, 14, 18 
2(d), 4, 14, 18 
Sep 28 
3 
2.2 
19, 20, 21, 22, 23, 24, 26 
19, 22, 26(b) 
Oct 5 
4 
2.3 
32, 34, 35 
32 
Oct 5 
4 
2.4 
37, 38, 41 
38 
Oct 12 
5 
3.1 
1, 2, 3, 4, 7, 8, 9, 10 
8 
Oct 12 
5 
10.2 
1, 2, 3, 6, 10, 11, 12 
6, 10 
Oct 12 
5 
4.1 
1, 2, 3, 5 
2 
Oct 19 
6 
4.2 
7, 8, 9, 10, 13, 14, 16, 18, 21 
8, 10, 18 
Oct 19 
6 
4.3 
25, 27, 28 
28 
Oct 26 
7 
5.1 
1, 2, 3, 4, 5, 6 
4, 6 
Oct 26 
7 
5.2 
9, 11, 12, 16 
12, 16 
Nov 9 
8 
5.3 
18, 19, 21, 22, 24, 25, 27 
18, 22(a), 24 
Nov 9 
8 
6.1 
1, 2, 4, 6 
4 
Nov 9 
8 
6.2 
9, 10, 11, 12, 13, 14, 16 
14, 16 
Nov 16 
9 
9.1 
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 
6, 14(a, b) 
Nov 16 
9 
(9.1) 
12, 14, 17, 19, 22 
14(c), 22 – extra cred 
Nov 18 
A 
10.1 
(10.2) 4, 8, 9 
4, 8 
Nov 30 
10 
10.3 
17, 18, 19, 20 
18 
Nov 30 
10 
(10.3) 

20 – extra cred 
Dec 9 
B 
8.1 
1, 2, 3, 6, 7, 8, 11, 12, 13, 
6(a) 
Nov 30 
10 
(8.1) 
14, 16 
14 
Dec 7 
11 
(8.1) 

6(b), 16 – extra cred 
Dec 9 
B 
8.2 
17, 18, 19, 21, 24, 25, 27, 31, 32 
32 
Dec 7 
11 
There is one project due on Nov 23 with a proposal
due on Nov 9.
You are to select a research paper written about a topic in Graph theory from
the list below that was published some time after 1999.
Interval
graphs
Perfect
graphs
Clique covering
number
List
colorings of graphs
Crossing
number
Thickness
Tree width
Rigidity
Visibility
graphs
Graph
labeling
Pebbling
Ramsey
Theory  other than what is covered in section 11.1
Get a copy of the paper. Read the paper,
including the proofs. Look up terms that you do not know from class or
our book, using another source. Write a report. Your report should
contain:
Section 1:
Title of the paper
Name(s) of the author(s)
Journal
Volume, section
Date
Pages
Section 2:
An explanation of the main
result(s) in your words
Include definitions of terms
that were not covered in our course.
Section 3:
A sketch of one of the
proofs. Be sure to say which result you are giving a proof of.
Your comments.
Section 4:
Attach a copy of the paper.
I suggest that you start this early and obtain
several papers. Skim reading them before choosing one for your
report. To obtain the papers, start with MathSciNet. You can access
this via the Math Dept. web page under "Web Resources". Do a
full search and enter 05C under "MSC Primary". Find a paper in
one of the following journals so that you can quickly obtain it either from the
library or online, as long as you are using a URI computer.
Discrete
Applied Mathematics
Electronic
Journal of Combinatorics
Journal
of Graph Theory
Journal
of Combinatorial Theory, Series B
Discrete
Math
Annals
of Combinatorics
European
Journal of Combinatorics
Journal
of Discrete Algorithms
Tests will draw from material covered in class,
that is, any theorems, proofs, example, or homework problem that we actually
discuss in class is possible material for the tests. So, the best way to
prepare for the tests will be to start with your class notes. Notice that
implied in the last sentence is that you should take notes! There will be 2,
75minute exams and a final. The hour exams will be given on Oct 14 and Dec 2 and the final
will be on Dec 16.
Your grade will be based on your test scores,
final exam score and homework grades. The scores are averaged and then weighted
to compute your final grade according to the following percentages.


Homework 
25% 
Project 
10% 
2 tests 
40% 
Final 
25% 