Loosely speaking, graphs are basically a set of objects, or vertices (nodes), taken together with a set of inter-node relationships, called edges. Graph theory is a relatively new area of mathematics that has recently become increasingly popular due to its far reaching spectrum of use. Its oigins were in daily applications to bridge routes and chess and its study preserves this practice. Graph theory is different in the sense that one can both color with crayons and do a proof by induction all in one day's work, which is one reason why it has been often labelled as one of the more fun and enjoyable aspects of mathematics!
Graphs as mathematical objects form the basis of our study, a continuing investigation whose beginnings go back to the great mathematician Leonhard Euler. We will begin our study there and build our way up to modern aspects and applications of graph theory.
- Lesson 1: What is a graph?
This lecture is the opening lecture in the Introduction to Graph Theory series. It is a very rough basic overview of some introductory material we will need to know for future lessons.
We are following (almost exactly) the Graphs & Digraphs, Fifth Edition book by Gary Chartrand, Linda Lesniak, and Ping Zhang. This video covers the opening chapter.
Length: about 1 hour. We want to make a special note that this is the first video we have ever edited and made, especially in the way of teaching. We are open to constructive criticism, as we want you guys to be able to learn from this! We are using a Wacom Bamboo tablet to capture our writing, and Camtasia software to record on screen. If you guys have any suggestions, we want to hear them before we make too many of these videos! :D
- Lesson 2: Degrees in Graphs (Sequences)
Lesson 2 covers topics such as degree sequences, the Havel-Hakimi theorem and algorithm, the Erdos-Gallai Theorem, and the "Party Problem"!
We have also greatly improved the teaching methods in Lesson 2. Hopefully you guys will enjoy this one more, and you'll learn something, too!
- Lesson 3: Paths, Cycles, and Periphery
Lesson 3 covers topics such as walks, paths, cycles, circuits, distance, adjacency matrices, and periphery!
We are still using the improved lecture method here. This video is about 30 minutes long. Enjoy!
In terms of mathematical prerequisites, experience with Combinatorics, Number Theory, or just general Discrete Mathematics is ideal. There will be logic involved, and proof methods, so any experience with that is good as well. There may be a few summations here and there, but no integrals, gradients, derivatives, or topological spaces will be involved.
We want to make this accessible to everyone, so if needed we can definitely explain!
Alright, guys, tentative syllabus is up! Please remember that I want to be really flexible with this class, and if I get requests for more material on certain subjects, we can omit the probabilistic stuff at the end, or edit the syllabus in the middle as we need to!
Materials will be hosted on this University of Reddit site and on the accompanying subreddit, r/IntroToGraphTheory. We are going to try to cover many bases here, and the syllabus will be subject to change. We will do at least one lesson a week covering the materials listed, so check in regularly!
(Also, keep in mind, even though I don't post applications of sections in the syllabus, I plan on covering applications at least briefly in every section, when applicable.)
Week 1: An Introduction to Graphs and Digraphs.
- Degree Sequence
- Graph Isomorphisms
- Connected Graphs and Distance
- Digraphs and Multigraphs
Week 2: Trees and Connectivity
- Nonseparable Graphs
- Spanning Trees
- Connectivity and Edge Connectivity
- Menger's Theorem
Week 3: The Structure of Graphs
- Bridges, Cut-Vertices, and Blocks
- The Graph Reconstruction Conjecture
Week 4: Eulerian and Hamiltonian Graphs
- Eulerian Paths and Cycles
- Hamiltonian Paths and Cycles
Week 5: Planarity
- The Euler Identity
- What is planarity, and what is nonplanarity?
- Hamiltonian Planar Graphs
Week 6: Graph Colorings
- Vertex Colorings
- Edge Colorings
Week 7: Matchings, Factors, and Decompositions
- Matchings and Independence in Graphs
- Factorizations and Decompositions
- Graph Labelings
Week 8: Domination in Graphs
- The Domination Number of a Graph
- Independent Domination
- Other Domination Parameters
Week 9: Ramsey Theory
- Classical Ramsey Numbers (Not sure what else in Ramsey Theory we'll cover here, tentative for now!)
Week 10: The Probabilistic Method in Graphs
- The Probabilistic Method
- Random Graphs
Message us anytime if you have any questions!!
My fiance and I are senior mathematics majors at a relatively small university in the USA where the mathematics faculty puts emphasis on discrete mathematics. We have done a good deal of mathematics research in number theory, probabilistic methods, and graph theory and hope to each have about five publications by graduation, pending acceptance, of course! Additionally, each of us have presented our research at national conferences including the Joint Meetings in Mathematics, MathFest, and smaller regional conferences. We have taken undergraduate graph theory, combinatorics, number theory, and abstract algebra courses (not counting the others we've taken!) and we have both tutored in each area. We're just trying to get more people interested in mathematics and hopefully inspire a few folks!