Table of topics and assignments 

Textbook: Graph Theory by Ronald Gould, Dover, (2012). The sections and problems recorded below correspond to this textbook.

Very Important Link: Professor Ram's Notes and other materials on Graph Theory

TA: Justin Wisby        Email: jwisb001@fiu.edu              Help Hours: MW 7-8pm via zoom  https://fiu.zoom.us/j/98511063156?pwd=MU9hb2JhRFVGOTdhR2YxNnZLRmdxQT09

I will generally follow Professor's Ram's notes for the course, although my style of presentation may be different at times. I encourage you to read Professor's Ram's notes in parallel with the corresponding material from the textbook. Best would be to do this reading even before we cover the topics in class. The Suggested Assignments list below will generally mirror the Homework Sheet from Professor Ram's Graph theory webpage above. You also have solutions to those problems on his webpage, sample old exams, review sheets and other useful materials. Professor Ram's page has a link to pdf files of the relevant chapters of the textbook.

Added after week 2: Below are links to three Lectures on proofs delivered at MIT by Prof. Tom Leighton. Please watch them if you have not had a good exposure to proofs before.

Lecture 1                               Lecture 2                                Lecture 3

Day# Date Topics Covered Suggested assignment Comments
0     Check the syllabus and start reading -- Chapter 1 Basic concepts of Graph Theory
from Professor Ram's notes for Graph Theory and from the textbook		  
1 1/11 Basic defs +  Degree sequence of a graph;
Graphical sequence thm
(H.H. thm)
 
2 1/13 Proof of H.H. theoreom
Graph recovery algorithm		 For Chapter 1 (p. 27-30 textbook): 1, 5, 6, 7 (except the part about G1[G2]), 9, 10, 12, 13, 14, 16-20all, 23-25all, 27-29all

Problem 21 regarding the degree set  is NOT a part of your suggested assignment, but, if you are curious, here is a nice (and fairly recent !) one-page paper that solves it.  

This is your first hand-in homework. It is due Thursday, Jan. 20 (see rules on the right)

 Homework rules: I accept individual or group submissions for homework with the following conditions:
(i) groups should have at most 4 people;
(ii) each person in the group should contribute to the homework, ideally by writting some parts of it for the group;
(iii) initials of the person who wrote a problem should be clearly marked.
(iv) work should be clean, multiple sheets stapled.
3 1/18 More basics - Walks, trails, paths, cycles;
Isomorphisms of graphs		 For Chapter 1 (p. 27-30 textbook): 1, 5, 6, 7 (except the part about G1[G2]), 9, 10, 12, 13, 14, 16-20all, 23-25all, 27-29all  
4 1/20 Common families
and operations on graphs.		 Worksheet 1/20 You do NOT have to turn in the worksheet 1/20 (you already did turn in page 1 in class), but consider all problems on it as additional suggested assignment.
5 1/25 Representations of graphs. Adjacency matrix and counting walks.    
6 1/27 BFS algorithm Worksheet 1/27 Due Thursday, Feb. 3.
Here are the best student solutions for Worksheet 1/27:
From Carlos Miguel Garcia              From Michael Ilyin
Note they had different ideas for the algorithm of Pb. 4, neither one perfect, but I think they could be adapted to work.
Actually, here is my attempt to an algorithm for Pb. 4, close to Michael's idea.
  
7 2/01 Connectivity For Chapter 2 (p. 64-66 textbook): 1, 3, 5, 7, 10, 15, 25-30all, 34-37all (from your edition of the textbook) Courtesy of Prof. Ram, you can find solutions to almost all problems in the suggested hwk on the right. Numbering of the problems is slightly different, as he used an older edition of the textbook when he wrote those solutions.
8 2/03 Distance in weighted (labelled) (di)graphs; Dijkstra's algorithm. Worksheet 2/03 (stolen from Prof. Ram's Exam 1- Spring 2017) During quarantine, I discovered the following Youtube Graph Theory videos. You may find them useful, as many of the class topics are also treated in those videos (but you need to do some searching):
1. Videos from Sarada Herke
2. Videos from Wrath of Math
9 2/08 Trees For Chapter 3 (p. 101-103 textbook): 1, 2, 3, 5, 6, 9, 10, 17, 18, 27 (from your edition of the texbook) The suggested problems for Chap. 3 correspond identically to Prof. Ram's hwk problems, but again the numbering is slightly different. In any case, you have solutions for all of them.
10 2/10 Minimal weight spanning trees; Kruskal's Algorithm; Prim's Algorithm. Worksheet 2/10 (This is now a homework due Tuesday, Feb. 15)
The table corresponding to the application of each algorithm should appear in your solution.
Solution key of Worksheet 2/10 (from the paper of Tao Lin)		 The lecture notes are available in Canvas. You can look at Prof. Ram's notes as well for different examples of each Kruskal's and Prim's algorithms.
11 2/15 Prufer's coding and decoding algorithms;
Cayley's Theorem		    
12 2/17 Rooted trees and optimal binary codings Worksheet 2/17 -- Pb. 3 from Prof. Ram's Test 1 - Fall 2017 (not collected)  
13 2/22 Review for Exam 1 You can use this Review guide for Exam 1  
14 2/24 Exam 1
in room OE 105		 Solution key for Exam 1

Homework 3 -- due Thursday, March 10		 Homework 3, on the left, involves some reading ahead.
I will cover Euler's circuits theorem in class after the break, but it would be good if you start the homework already.
Have a good Spring break!
15 3/08 Eulerian graphs For Chapter 5 (p.162-166 textbook): #1, 2, 4, 10, 11, 15-19all, 49  
16 3/10 Fleury's algorithm;
Postman problem		 Worksheet 3/10  
17 3/15 Hamiltonian cycles
and paths		    
18 3/17 Hamiltonian cycles
and paths		   I recommend that you watch all videos from Sarada Herke on Hamiltonian cycles and graphs. The proof that Petersen's graph is not Hamiltonian is required.
19 3/22 Euler Planarity formula For Chapter 6 (p. 198-200 textbook): #1, 2, 5, 7-12all, 14, 16  
20 3/24 Planar graphs/ Kuratowski's Thm Worksheet 3/24  
21 3/29 DMP algorithm   Exam 2 is moved to Thursday, April 14.
It will be held in room OE105. Exam 2 will cover
Chapters 5, 6, and partly 8 (graph colorings).
More details to come.
22 3/31 Graph embeddings in other surfaces;
Polyhedra & the five regular polyhedra Thm.		 Worksheet 3/31 This worksheet will NOT be collected, but solve the problems on it, as exam preparation.
23 4/05 The five regular polyhedra Theorem;
More on previous worksheet		 Mini quiz 4/05  
24 4/07 Graph Coloring    
25 4/12 Heawood's 5 color Thm.
Review for Exam 2		 Review guide for Exam 2  
26 4/14 Exam 2 Solution key for Exam 2  
27 4/19 Matchings in graphs    
28 4/21 More matchings
Hall's Theorem		 Review guide for the Final Exam  

Final Exam, on Tuesday, April 26, 9:30-11:45 am, in OE 105