the cedar ledge

Achieving an Undergraduate Level Understanding of Graph Theory

Date: December 31 2022

Summary: Ultralearning project to learn the equivalent of an undergraduate maths of computer science student understanding of graph theory.

Keywords: #zettel #ultralearning #graph #theory #project #archive #blog


Not Available

Table of Contents

        1. Procedures
    1. Roadmap
  1. How To Cite
  2. References:
  3. Discussion:


I have always found graph theory interesting ever since I was exposed to it back in my undergraduate studies at Georgia Tech. I found out about it through SIR Modeling but personally found the structure of graphs far more fascinating than its application to SIR models. Furthermore, as I intend to be pursuing graduate studies in applied mathematics, why not get started with trying to understand it?

Project Goals

This process is adapted from the Ultralearning framework posited by Scott Young.

What Am I Doing?

Gain an undergraduate level of understanding of graph theory on par with maths and computer science students.

  1. Representing graphs using different notations (e.g. adjacency lists, adjacency matrices, incidence matrices).

  2. Traversing graphs using different algorithms (e.g. breadth-first search, depth-first search).

  3. Analyzing the properties of graphs (e.g. connectedness, bipartiteness, acyclicity).

  4. Finding paths and circuits in graphs.

  5. Identifying and constructing different types of trees (e.g. rooted trees, binary trees).

  6. Coloring the vertices or edges of a graph according to various coloring schemes (e.g. vertex coloring, edge coloring).

  7. Finding matchings and factors in graphs.

  8. Identifying and constructing Hamiltonian cycles in graphs.

  9. Modeling and analyzing flow problems in graphs using network flows.

  10. Applying group-theoretic and logical techniques to analyze graphs.

  11. Applying geometric techniques to analyze graphs.


This is based on the Meta Learning step Young described as well as some additional tweaks of my own:

Definition of a graph and its components[1], [2]Graph components; differences between directed and undirected graphs
Subgraphs and isomorphism[1], [2]Subgraphs; isomorphism; identify and compare given graphs
Directed graphs[2]Directed graph; representation using adjacency and incidence matrices
Graphs and their properties[1], [2]Properties of graphs; analyze; classify different types of graphs
Paths and circuits[1], [2]Paths and circuits; identify and construct given graph
XConnectedness and components[1]Determine if graph is connected; identify graph components
Distance in graphs[1], [2]Vertex distances; compute vertex distances
Trees and their properties[1], [2]Tree definitions; identify trees; distinguish trees
Rooted trees and binary trees[1], [2]Rooted trees; construct and manipulate rooted trees
Adjacency matrices[1]Adjacency matrix concept; representation of adjacency matrix
Incidence matrices[1]Incidence matrix concept; representation of incidence graphs
Breadth-first search[1], [2]Breadth-first search concept; graph traversal
Depth-first search[1], [2]Depth-first search concept; graph traversal
Planar graphs and their properties[1]Planar graph definition; properties
Euler's formula[1], [2]Euler's formula; structure of planar graphs
Dual graphs[1]Dual graph concept; construction of dual graph
Vertex coloring[1], [2]Vertex coloring concept; coloring of graph vertices
Edge coloring[1], [2]Edge coloring concept; coloring of graph edges
Matchings[1], [2]Matching concept; identification and construction
Factors[1]Factor concept; identification and construction
Hamiltonian cycles[1], [2]Hamiltonian cycle concept; identification and construction
Network flows[1]Network flow concept; modeling and analysis
Graphs and groups[2]Graph and group theory connection; analysis
Graphs and logic[2]Graph and logic connection; analysis
Graphs and geometry[2]Graph and geometry connection; analysis

This table describes the very broad topics, resources I'll use, and the expected learning outcomes for each topic. As I progress through this table, I will add an "X" to each row I have studied. Furthermore, the table is ordered by level of difficulty with "Definition of a graph and its components" being the first topic I should learn and "Graphs and geometry" being the more advanced topics I should study. The topics and resources here are based on [1] and [2] with potentially more resources to add in the future.

DoneSkill LevelTopicConcept
BeginnerFundamental conceptsPaths
BeginnerFundamental conceptsCycles
BeginnerFundamental conceptsSubgraphs
BeginnerFundamental conceptsIsomorphism
BeginnerTreesSpanning trees
BeginnerConnectivityMax-flow Min-cut theorem
BeginnerConnectivityMenger's theorem
BeginnerEulerian and Hamiltonian graphsEulerian and Hamiltonian graphs
BeginnerMatchingsHall's theorem
BeginnerMatchingsTutte's 1-factor theorem
BeginnerColoringsGreedy coloring
BeginnerColoringsChromatic polynomial
BeginnerPlanar graphsEuler's formula
BeginnerPlanar graphsKuratowski's theorem
BeginnerPlanar graphsEquivalents of the 4-color theorem
BeginnerRamsey theoryRamsey's theorem
IntermediateStructure of 1-, 2-, 3-connected graphsBlocks
IntermediateStructure of 1-, 2-, 3-connected graphsEar-decomposition
IntermediateStructure of 1-, 2-, 3-connected graphsContractible edges
IntermediatePerfect graphsBipartite graphs
IntermediatePerfect graphsComparability graphs
IntermediateTutte's synthesis of 3-connected graphsTutte's synthesis of 3-connected graphs
IntermediateSystems of distinct representativesSystems of distinct representatives
IntermediateMatching polytopeMatching polytope
IntermediateChinese postman problemChinese postman problem
IntermediateDual graphsDual graphs
IntermediateGraphs on surfacesGraphs on surfaces
IntermediateHighly chromatic graphs of large girthHighly chromatic graphs of large girth
IntermediateVizing's theoremVizing's theorem
IntermediateErdos-de Bruijn compactness theoremErdos-de Bruijn compactness theorem
AdvancedLine graphs of bipartite graphsLine graphs of bipartite graphs
AdvancedChordal graphsChordal graphs
AdvancedComplements of the aboveComplements of the above
AdvancedPerfect Graph TheoremPerfect Graph Theorem
AdvancedDilworth's theoremDilworth's theorem
AdvancedApplications of Ramsey's theoremApplications of Ramsey's theorem
AdvancedLower bound for Ramsey numbersLower bound for Ramsey numbers
AdvancedProperties of random graphsProperties of random graphs
AdvancedThreshold functionsThreshold functions
Advanced0-1 law0-1 law

This table gets more into exact topics and concepts to master. They have an associated difficult level and overall topic. Moreover, this a synthesis of concepts and topics to be covered based on class outlines from:

How To Cite

Zelko, Jacob. Achieving an Undergraduate Level Understanding of Graph Theory. December 31 2022.


[1] R. Trudeau, Introduction to Graph Theory, Dover. DOVER PUBLICATIONS, INC., 1994.

[2] N. Hartsfield and Ringel, Pearls in Graph Theory A Comprehensive Introduction. DOVER PUBLICATIONS, INC., 1994.


CC BY-SA 4.0 Jacob Zelko. Last modified: July 16, 2023. Website built with Franklin.jl and the Julia programming language.