MTH 607 Graph Theory Course Outline

• Basic Definitions.
• Standard graphs (K_n, P_n, C_n, K_m,n, Peterson).
• Incidence structures.
• Bipartite Graphs.
• Subgraphs, including induced subgraphs.
• Union and complement of graphs.
• Digraphs.
• Paths and circuits.
• Connectivity (includes cut point, Articulation points, cut edge, cut set, k-edge connected, k-vertex connected, strongly connected, weakly connected).

Practice problems

Section	Page	Exercises
1.1	7	2, 3, 4, 5, 10.
1.2	17	11, 12, 15, 16, 20.
1.3	25	21, 24, 27.
1.4	28	29, 31, 22, 33.

• Degree
• Regular graphs
• Degree Sequences
• Matrices and Walks (includes application to length of paths, number of walks).

Practice problems

Section	Page	Exercises
2.1	36	1, 2, 4, 7, 9, 10, 14, 17.
2.2	41	19, 21, 25, 27.
2.3	47	32, 33, 35.
2.4	49	37, 40, 41.

• Isomorphism in graphs

Practice problems

Section	Page	Exercises
3.1	61	1, 2, 3, 5, 8, 9, 10, 13, 15.
3.2	65	17, 19.

• Big O notation and complexity classes
  See also Epp section 9.2.
• Representing Graphs
• Adjacency lists and incidence matrix
• Depth First Search (DFS) and Breadth First Search (BFS)
• Algorithms

• Trees (including rooted trees and binary trees).
• Spanning Trees.
• Kruskal and Prims algorithms.

Practice problems

Section	Page	Exercises
4.1	89	1, 2, 3, 5.
4.2	92	7, 9, 10, 13, 17.
4.3	99	25, 26, 27, 30.

• Ring Sums, Fundamental Circuits and Cut Sets.
• Definitions, including Edge cuts and edge Connectivity
• Whitney's 1st Theorem (κ(G) ≤ λ(G) ≤ δ(G))
• Blocks and 2-connected graphs
• Whitney's 2nd Theorem (2-connected ⇔ every pair of vertices is joined by 2 internally disjoint paths). Note that this is a special case of Menger's Theorem below.
• Characterization of blocks/2-connected graphs.
• Menger's Theorem

Practice problems

Section	Page	Exercises
5.1	110	1, 3, 5, 7*.
5.2	114	9, 12, 13, 16.
5.3	122	17, 18, 19, 21, 23, 25, 29, 31.
5.4	129	34, 35, 37.

• Euler circuits - Eulers Theorem.
• Hamiltonian circuits.

Reading 6.4.

Practice problems

Section	Page	Exercises
6.1	140	1, 3, 4, 7.
6.2	150	9, 11, 13, 15, 23.

Matchings

• Definition of matching
• Applications
• Unions and ring sums of matchings
• M-augmenting paths - Berge's Theorem.
• Matchings in bipartite graphs: Saturating matchings and Hall's Theorem.
• Corollary to Hall's: Every k-regular bipartite graph has a perfect matching.

  Edge covers and independent sets.

• Definitions and examples

  Factors and Factorizations

• Matchings and 1-factors, Tutte's Theorem.
• 1-factorizations, 1-factorizations of K_n and C_n for n even.
• 2-factors, decomposition into cycles.
• Hamiltonian decompositions.
• Triangle factors (Kirkman)
• Decompositions of graphs - Triple systems
• Algorithms - Backtrack and Hill climb.

Reading 8.4, 8.5.

Practice problems

Section	Page	Exercises
8.1	192	1, 2, 3, 7, 9, 10, 11, 13, 14, 15, 16.
8.2	207	17, 19, 21, 23, 25, 27, 29, 30, 31, 32.
8.3	213	33, 35, 36, 34, 37.

• Graph colourings
• Clique number
• Interval graphs
• The greedy algorithm
• Brookes Theorem
• Edge colourings.
• Bipartite graphs
• Vizings Theorem

Reading 10.1.

Practice problems

Section	Page	Exercises
10.2	277	1, 2, 3, 5, 8cde, 11, 13, 16.
10.3	287	17, 19, 20.