Math 3V03 -- Graph Theory
(Fall 2015)

This course is an introduction to graph theory.

News (Last Updated: December 7, 2015)

Below is a summary of what we did in class, plus any relevant news and/or information.

During the week of December 7-11, my office hours will be: M: 12:30-1:30, W: 1:00-3:00, and Th: 9:30-1:30, 1:30-3:00. You can also email me your questions.
December 7, 2016 Today was our last class. I went over the material of Section 10.3 on the connection between graphs and topology. I also handed back the last assignment and the project.
December 3, 2015 We started Chapter 10 today. I described how to put a rotation on a graph, and how to define a planar graph using the notion of a rotation. HWA 9 and the project were collected.
December 2, 2015 We finished Chapter 9 today by looking at the material on m-pires.
November 30, 2015 We looked at the thickness and splitting numbers of a graph (see Section 9.2). HWA 8 is graded and will be handed back on Wednesday. However, you can come by my office if you want them earlier.
November 26, 2015 Today we started Chapter 9; the focus of this chapter is measuring how close a graph is to being planar. In particular, we discussed Kuratowski's Theorem and the crossing number.
November 25, 2015 I added the Final Exam Information Sheet to the webpage.
November 25, 2015 We finished up Section 8.3, and quickly went through some of the material of Section 8.4 on drawing graphs. In particular, we discussed how to draw planar graphs using only straight lines.
November 23, 2015 We started Section 8.3 which is focused on giving a proof of the Five Colour Theorem.
November 19, 2015 Today we finished our our discussoin of the four colour theorem (Section 8.2). HWA 7 was due in class today, while I assigned HWA 8.
November 18, 2015 We continue our discussion of planarity by spending the first of two lectures on 8.2 which discusses the four colour theorem for planar graphs.
November 16, 2015 We started Chapter 8 on planar graphs today. We covered all of Section 8.1. I also handed back Midterm II.
November 12, 2015 We had Midterm II today. I have posted the solutions on this webpage. See to the right.
November 11, 2015 In class, we spent more time discussing how to use SAGE to find anti-magic labellings. I also handed back HWA 6.
November 9, 2015 For Monday and Wednesday, we will be looking at the conjecture that every tree is anti-magic. In particular, our goal for the next two days is to start to develop code in Sage to test a conjecture. See below for the code used in today's class.
November 5, 2015 We finished Chapter 7 on algorithms by discussing how to find a prefix code and use Hoffman's Algorithm.
November 4, 2015 In today's class I showed how the Hungarian algorithm can be used to find a maximal matching in a bipartite graph (see Section 7.2).
November 2, 2015 Today we started Chapter 7 by going over the material of Section 7.1 I introduced an algorithm to find a spanning tree in a graph, and an algorithm (Kruskal's Algorithm) to find the spanning tree of minimal weight.
October 29, 2015 We went over the material of Section 6.2 on conservative graphs. You should also know what we mean by a digraph. HWA 5 was collected and HWA 6 was assigned.
October 28, 2015 In today's class, we looked at magic graphs, and proved that in some cases a graph has a magic labelling. I also mentioned anti-magic graphs. We will return to this. Today's material covered Section 6.1
October 26, 2015 We finished Chapter 5 on counting by counting the number of spanning trees of complete bipartite graphs. Please note that today's office hours will be cancelled.
October 22, 2015 We looked at Section 5.3 on Cayley's Spanning Tree Formula. You should know how to use Prufer's method.
October 21, 2015 In today's class we started the chapter on counting. In particular, we derived a formula for the dearrangement, which counts, among other things, the number of 1-factors in the a complete bipartite graph minus a 1-factor.
October 19, 2015 Welcome back from the break. We finished up Chapter 4 by covering the material of Section 4.3 on Ramsey numbers.
October 8, 2015 We had the first midterm. It will be returned after the break. Here are the solutions.
October 7, 2015 Today, I introduced the class to SAGE and how to use it to do problems in graph theory. I also incorporated some review questions. HWA 4 was also assigned.
October 5, 2015 Class was held in the library today. You learned aobut the resources available for your math project.
October 1, 2015 In today's class we looked at the problem of finding cages. This is the material of Section 4.2. HWA 3 was due in class. I did not give out a new HWA -- instead, you should study for your midterm and work on your project.
September 30, 2015 We started looking at Section 4.1. You should know what we mean by extremal graph theory, and you should know Turan's theorem.
September 28, 2015 Today we looked at some futher decomposition results found in Section 3.2. We will not cover Section 3.3. The first midterm will cover up to today's material. I also handed back HWA 2.
September 24, 2015 We finished Section 3.1 by discussing Eulerian graphs. HWA 2 was also due in class.
September 23, 2015 We wrapped up Section 2.4, and started Section 3.1 by showing that an graph can be decomposed into cycles if and only if every vertex has even degree.
September 21, 2015 Today we went over the material of Section 2.3. You should know what we mean by a decomposition of a graph. You should also know what a Hamilton cycle and path are. I returned HWA 1. I will be changing my office hours to M 12:30-11:30 and W 11:30-12:30.
September 17, 2015 We went over the material of Section 2.2 on edge colorings today. You should know what me mean by an edge coloring, a regular graph, a snark. In addition, we computed the edge chromatic number of the complete graphs. The first homework assignment was collected, the second one was assigned.
September 16, 2015 In today's class we went over some of the properties of trees. We also introduced the notion of colouring of graphs and critical graphs. We covered the rest of Section 1.3 and Section 2.1.
September 14, 2015 Today we covered Sections 1.2 and part of 1.3. We also finished up a proof on valid degree sequences.
September 10, 2015 We went over the material of Section 1.1 the text. After today's class, you should know the Handshaking Theorem. In addition, you should also know what a degree sequence is, and how to determine if a degree sequence is valid. HWA 1 was also assigned.
September 9, 2015 Today was the first day of class. We went over the course handout and tried some problems related to graph theory.
August 24, 2015 A revised version of the course outline added to the web, plus the first two assignments.
August 12, 2015 The website went live. The course information sheet was added to the webpage (see to the right).

Using SAGE

As part of this class, we will spend a couple of days talking about how to use SAGE to do computations with SAGE. Here are some important links.

SAGE Math Website This is the main website for the SAGE Math program. You have two options for running SAGE: you can do it online through your browser, or you can download it to your computer.
SAGE Tutorial A tutorial on how to use SAGE. Check it out!
Video on SAGE and Graph Theory I highly recommend watching this 25 minute video. It will give you a sense of what you can do with SAGE. Note that not all the information will be relevant.
Algorithmic Graph Theory and Sage A book by David Joyner, Minh Van Nguyen, and David Phillips that incorporates lots of SAGE code. Good for finding examples.

Here is the code we used in class on October 8:


# SAGE Tutorial for Math 3V03
#
# Inputting a Graph via a list

g = Graph({0:[1,2,3,4], 1:[2,5], 2:[5], 3:[4,5], 4:[5]})

# Inputting a Graph via built-in commands I
h = graphs.HeawoodGraph()



# Inputting a Graph via built-in commands II
l = graphs.CompleteGraph(7)


# The plot command

plot(g)
plot(h)
plot(l)

# The show command

show(g)
show(h)
show(l)


# how to save a graph

plot(h).save('graphHeawood.pdf')


# basic commands
# list edges

g.edges()
h.edges()
l.edges()


# list vertices and degrees

g.vertices()
g.degree()
g.degree(2)


# checking k-regular

g.is_regular()
h.is_regular()


# computing girth
g.girth()
h.girth()


# chromatic number 
g.chromatic_number()
h.chromatic_number()
h.is_bipartite()


# Sec 1.1 - Degree Sequences

DS = DegreeSequences(7)
[5,4,4,3,2,1,1] in DS
m = graphs.DegreeSequence([5,4,4,3,2,1,1])
plot(m)


[6,3,3,3,3,3,3] in DS
plot(graphs.DegreeSequence([6,3,3,3,3,3,3]))


# Sec 1.2 - Subgraphs
gg =g.subgraph([0,1,2,5])
plot(gg)


# Sec 1.3 - Trees

k=g.spanning_trees()
g.spanning_trees_count()
plot(k[1])

# sample loop

for i in range(10):
    plot(k[i])

# Sec 2.1 - Colouring

g.chromatic_number()
gg.chromatic_number()
h.chromatic_number()

# Sec 2.2 - Edge Colouring

from sage.graphs.graph_coloring import edge_coloring
edge_coloring(g)

# Sec 2.3 - Hamiltonian Cycles

h.hamiltonian_cycle()
h.hamiltonian_cycle(algorithm='backtrack')

# Sec 2.4 - Bridges

g.bridges()
f = graphs.FibonacciTree(5)
plot(f)
f.bridges()

# Sec 3.1 - Eulerian circuits

g.eulerian_circuit()
h.eulerian_circuit()
l.eulerian_circuit()

Here is the code we used in class on November 9:

A1 = Matrix(6,[0,1,1,1,1,0, 1,0,0,0,0,0, 1,0,0,0,0,0, 1,0,0,0,0,0,
 1,0,0,0,0,1, 0,0,0,0,1,0])
print(A1)
T = Graph(A1)
plot(T)
 
W1 = Matrix(6,[0,1,3,5,2,0, 1,0,0,0,0,0, 3,0,0,0,0,0,
 5,0,0,0,0,0, 2,0,0,0,0,4, 0,0,0,0,4,0])
T1 = Graph(W1)
plot(T1)
 
L = T1.degree()
print(L)
print len(L)
S = set(L)  # get unique elements
print(S)
print len(S)
len(L) == len(S)
 
# A bad labelling
W2 = Matrix(6,[0,1,5,4,2,0, 1,0,0,0,0,0, 5,0,0,0,0,0, 4,0,0,0,0,0, 
 2,0,0,0,0,3, 0,0,0,0,3,0])
print(W2)
T2 = Graph(W2)
show(T2)
L = T2.degree()
print(L)
print len(L) # print out the degrees = sum of labels
S = set(L)  # get unique elements
print(S)
print len(S)  # count the number of unique elemetns
len(L) == len(S) # Will be false because two of the vertices have the same degree

Here is the code we used in class on November 11:


# Graphs and Adjaceny Matrices
T = Graph({1:[2,3,4,5],5:[6]})
plot(T)
W = T.adjacency_matrix()
print(W)
 
# A way to give a tree a labelling
# replacing 1's in adjacency matrix with labels 1n
count = 1
for i in range(0,5):
      for j in range(i+1,6):
          if W[i,j] <> 0:
              W[i,j] = count
              W[j,i] = count
              count = count+1

print(W)
 
## Here's what the above graph looks like
TT=Graph(W)
plot(TT)
 
# 
# Combine with code from last class
# to check if labelling gives anti-magic labelling
L = TT.degree()
print(L)
print len(L)
S = set(L)  # get unique elements
print(S)
print len(S)
len(L) == len(S)
 
# Exercise
W = Matrix(6,[0,1,0,1,0,0, 1,0,1,0,1,0, 0,1,0,0,0,1,
    1,0,0,0,0,0, 0,1,0,0,0,0, 0,0,1,0,0,0])
T = Graph(W)
plot(T)
count = 1
for i in range(0,5):
     for j in range(i+1,6):
          if W[i,j] <> 0:
              W[i,j] = count
              W[j,i] = count
              count = count+1

print(W)
TT = Graph(W)
plot(TT)
L = TT.degree()
print(L)
print len(L)
S = set(L)  # get unique elements
print(S)
print len(S)
len(L) == len(S)
 
# We can access lots of graphs via SAGE
ListOfTrees = graphs.trees(6)
for T in ListOfTrees:
      print T.adjacency_matrix()
 
# combine all the pieces
# to find many anti-magic labellings at once
ListOfTrees = graphs.trees(6)
for T in ListOfTrees:
      W= T.adjacency_matrix()
      T = Graph(W)
      plot(T)
      count = 1
      for i in range(0,5):
          for j in range(i+1,6):
              if W[i,j] <> 0:
                  W[i,j] = count
                  W[j,i] = count
                  count = count+1
      print(W)
      TT = Graph(W)
      plot(TT)
      L = TT.degree()
      print(L)
      print len(L)
      S = set(L)  # get unique elements
      print(S)
      print len(S)
      len(L) == len(S)
      if len(L) == len(S):
          print 'Found an anti-magic labelling  :-) '
      else:
          print 'Did not find anti-magic labelling :-( '
      print

# Variation -- put numbers in reverse order
ListOfTrees = graphs.trees(6)
for T in ListOfTrees:
      W= T.adjacency_matrix()
      T = Graph(W)
      plot(T)
      count = 5
      for i in range(0,5):
          for j in range(i+1,6):
              if W[i,j] <> 0:
                  W[i,j] = count
                  W[j,i] = count
                  count = count-1
      print(W)
      TT = Graph(W)
      plot(TT)
      L = TT.degree()
      print(L)
      print len(L)
      S = set(L)  # get unique elements
      print(S)
      print len(S)
      len(L) == len(S)
      if len(L) == len(S):
          print 'Found an anti-magic labelling  :-) '
      else:
          print 'Did not find anti-magic labelling :-( '
      print

Official Polices

1. Policy on Academic Ethics. You are expected to exhibit honesty and use ethical behaviour in all aspects of the learning process. Academic credentials you earn are rooted in principles of honesty and academic integrity.

Academic dishonesty is to knowingly act or fail to act in a way that results or could result in unearned academic credit or advantage. This behaviour can result in serious consequences, e.g. the grade of zero on an assignment, loss of credit with a notation on the transcript (notation reads: Grade of F assigned for academic dishonesty), and/or suspension or expulsion from the university.

It is your responsibility to understand what constitutes academic dishonesty. For information on the various types of academic dishonesty please refer to the Academic Integrity Policy, located at: http://www.mcmaster.ca/academicintegrity/

The following illustrates only three forms of academic dishonesty:

plagiarism, e.g. the submission of work that is not one's own or for which other credit has been obtained.
improper collaboration in group work,
copying or using unauthorized aids in tests and examinations.

2. Policy regarding missed work. If you have missed work, it is your responsibility to take action. If you are absent from the university for medical and non-medical (personal) situations, lasting fewer than 3 days, you may report your absence, once per term, without documentation, using the McMaster Student Absence Form (MSAF). See Requests for Relief for Missed Academic Term Work

Absences for a longer duration or for other reasons must be reported to your Faculty/Program office, with documentation, and relief from term work may not necessarily be granted. In Math 3V03, the percentages of the missed work will be transferred to the final examination. Please note that the MSAF may not be used for term work worth 25% or more, nor can it be used for the final examination.

3. Student Accessibility Services. Students who require academic accommodation must contact Student Accessibility Services (SAS) to make arrangements with a Program Coordinator. Academic accommodations must be arranged for each term of study. Student Accessibility Services can be contacted by phone 905-525-9140 ext. 28652 or e-mail sas@mcmaster.ca. For further information, consult McMaster University's Policy for Academic Accommodation of Students with Disabilities.

4. Important Message. The instructor and university reserve the right to modify elements of the course during the term. The university may change the dates and deadlines for any or all courses in extreme circumstances. If either type of modification becomes necessary, reasonable notice and communication with the students will be given with explanation and the opportunity to comment on changes. It is the responsibility of the student to check their McMaster email and course websites weekly during the term and to note any changes.

Course Information

Instructor: Adam Van Tuyl

Office: Hamilton Hall 419
Office Hours: MW 12:30-1:30
Email: vantuyl@math.mcmaster.ca

Place and Time:

Class: MTTh 10:30-11:20 in Hamilton Hall 217

Textbook:

Perals in Graph Theory
by Nora Hartsfield and Gerhard Ringel

Homework Assignments

Homework is given out every Thursday, and will be due, at the beginning of class, the following Thursday. Assignments must conform to the guidelines in the course outline. Assignments are posted below.

Assignment 1 (Due: Sept 17)

Sec. 1.1 -- 2,4,5,6,7
Sec. 1.2 -- 1,2,5,7,9

Assignment 2 (Due: Sept 24) [REVISED!]

Sec. 1.3 -- 4,5,8,9
Sec. 2.1 -- 3,5,12,16
Sec. 2.2 -- 5,6,8,11

Assignment 3 (Due: October 1) [REVISED!]

Sec. 2.3 -- 7,15,17
Sec. 2.4 -- 2,4,10
Sec. 3.1 -- 5,6,9
Sec. 3.2 -- 1,2,8

Assignment 4 (Due: October 22)

Sec. 4.1 -- 2,4,8
Sec. 4.2 -- 1,2,6ab,7
Use SAGE to do 2.3.5, 2.3.6, 2.3.7, 3.1.1

Assignment 5 (Due: October 29)

Sec. 4.3 -- 1,4,5
Sec. 5.1 -- 2,3,4,12
Sec. 5.2 -- 1,2b,3,4,9

Assignment 6 (Due: November 5)

Sec. 5.3 -- 1,4,5,9
Sec. 6.1 -- 1,2,8,10
Sec. 6.2 -- 2d,4,8,9

Assignment 7 (Due: November 19)

Sec. 7.1 -- 1b,2,6,8
Sec. 7.2 -- 2
Sec. 7.3 -- 1,3,5
Working in groups up to three, verify anti-magic conjecture for all 47 non-isomorphic trees on 9 vertices. SAGE is required.

Assignment 8 (Due: November 26)

Sec. 8.1 -- 5,6,11,15,16
Sec. 8.2 -- 1,2,3
Sec. 8.3 -- 1,3,7

Assignment 9 (Due: December 3)

Sec. 8.4 -- 1,2,4,8,11
Sec. 9.1 -- 1,5,6,8,10,11
Sec. 9.2 -- 2,4,5
Sec. 9.3 -- 1,5

Handouts

All class handouts are available as PDF files.

Course Information
Course handout from first day of class

Midterm 1 Information Sheet
Handout describing first midterm

Midterm 1 Solutions
Solutions to the first midterm

Midterm 2 Information Sheet
Handout describing second midterm

Midterm 2 Solutions
Solutions to the second midterm

Final Exam Information Sheet
Handout describing final exam

Grading Scheme

Your final mark is broken down as:

Homework = 20%
Midterm (x2)= 30%
Project = 10%
Final Exam = 40%

Important Dates

Sept. 8, 2015
First semester classes begin

Oct. 8, 2015
Midterm 1

Oct. 9, 2015
Project topic due

Oct. 12-16, 2015
Fall Midterm Break (no classes)

Nov. 5, 2015
Project draft due

Nov. 12, 2015
Midterm 2

Nov. 13, 2015
Last day for cancelling courses without failure by default

Dec. 3, 2015
Project Due

Dec. 7, 2015
First semester classes end

Dec. 11, 2015
Final Exam at 9:00AM in BSB 120

Math 3V03 -- Graph Theory (Fall 2015)