**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

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?

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

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

Basic concepts:

Definition of a graph and its components:

Understand the components of a graph and the differences between directed and undirected graphs.

Subgraphs and isomorphism:

Understand the definitions of subgraphs and isomorphism and be able to identify and compare them in a given graph.

Directed graphs:

Understand the definition of a directed graph and be able to represent it using adjacency and incidence matrices.

Graphs and their properties:

Understand various properties of graphs and be able to apply them to analyze and classify different types of graphs.

Connectivity:

Paths and circuits:

Understand the definitions of paths and circuits and be able to identify and construct them in a given graph.

Connectedness and components:

Understand the concept of connectedness and be able to determine whether a graph is connected or disconnected.

Understand the concept of graph components and be able to identify them in a given graph.

Distance in graphs:

Understand the concept of distance between vertices and be able to compute it using various measures.

Trees:

Trees and their properties:

Understand the definition of a tree and be able to identify and distinguish trees from other types of graphs.

Rooted trees and binary trees:

Understand the concept of rooted trees and be able to construct and manipulate them.

Understand the concept of binary trees and be able to construct and manipulate them.

Spanning trees

Matrix representations of graphs:

Adjacency matrices:

Understand the concept of an adjacency matrix and be able to represent a graph using an adjacency matrix.

Incidence matrices:

Understand the concept of an incidence matrix and be able to represent a graph using an incidence matrix.

Graph algorithms:

Breadth-first search:

Understand the concept of breadth-first search and be able to implement it to traverse a graph.

Depth-first search:

Understand the concept of depth-first search and be able to implement it to traverse a graph.

Planar graphs:

Planar graphs and their properties:

Understand the definition of a planar graph and the properties that distinguish planar graphs from other types of graphs.

Euler's formula:

Understand Euler's formula and be able to apply it to analyze the structure of planar graphs.

Dual graphs:

Understand the concept of a dual graph and be able to construct the dual of a given planar graph.

Coloring graphs:

Vertex coloring:

Understand the concept of vertex coloring and be able to color the vertices of a given graph according to various coloring schemes.

Edge coloring:

Understand the concept of edge coloring and be able to color the edges of a given graph according to various coloring schemes.

Matchings and factors:

Matchings:

Understand the concept of a matching in a graph and be able to identify and construct matchings in a given graph.

Factors:

Understand the concept of a factor in a graph and be able to identify and construct factors in a given graph.

More advanced topics:

Hamiltonian cycles:

Understand the concept of a Hamiltonian cycle and be able to identify and construct Hamiltonian cycles in a given graph.

Network flows:

Understand the concept of network flows and be able to model and analyze flow problems in graphs.

Graphs and groups:

Understand the connection between graphs and group theory, and be able to apply group-theoretic techniques to analyze graphs.

Graphs and logic:

Understand the connection between graphs and logic, and be able to apply logical techniques to analyze graphs.

Graphs and geometry:

Understand the connection between graphs and geometry, and be able to apply geometric techniques to analyze graphs.

Definition of a graph and its components:

Vertices (also called nodes).

Edges.

Weights.

Labels.

Subgraphs and isomorphism.

Directed graphs and their representations:

Adjacency matrices.

Incidence matrices.

Graph properties:

Connected/disconnected.

Bipartite/not bipartite.

Cyclic/acyclic.

Paths and circuits.

Connectedness and components.

Distance between vertices.

Trees:

Definition.

Unique path between vertices.

Root vertex.

Branches.

Additional topics:

Matrix representations:

Adjacency matrices.

Incidence matrices.

Graph algorithms:

Breadth-first search.

Depth-first search.

Planar graphs and their properties:

Definition of a planar graph.

Properties that distinguish planar graphs from other types of graphs.

Euler's formula.

Dual graphs.

Tree properties:

Rooted trees.

Binary trees.

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

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

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

Finding paths and circuits in graphs.

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

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

Finding matchings and factors in graphs.

Identifying and constructing Hamiltonian cycles in graphs.

Modeling and analyzing flow problems in graphs using network flows.

Applying group-theoretic and logical techniques to analyze graphs.

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:

**Outcomes:**The knowledge and abilities youâ€™ll need to acquire for success.**Rationale:**Know exactly why you want to learn a skill or subject.**Resources:**The resources youâ€™ll use when learning.**Done:**If this task has been completed (X) or not yet (cell is empty)

Done | Topic | Resources | Outcomes |
---|---|---|---|

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 | |

X | Connectedness 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.

Done | Skill Level | Topic | Concept |
---|---|---|---|

Beginner | Fundamental concepts | Paths | |

Beginner | Fundamental concepts | Cycles | |

Beginner | Fundamental concepts | Subgraphs | |

Beginner | Fundamental concepts | Isomorphism | |

Beginner | Trees | Spanning trees | |

Beginner | Connectivity | Max-flow Min-cut theorem | |

Beginner | Connectivity | Menger's theorem | |

Beginner | Eulerian and Hamiltonian graphs | Eulerian and Hamiltonian graphs | |

Beginner | Matchings | Hall's theorem | |

Beginner | Matchings | Tutte's 1-factor theorem | |

Beginner | Colorings | Greedy coloring | |

Beginner | Colorings | Chromatic polynomial | |

Beginner | Planar graphs | Euler's formula | |

Beginner | Planar graphs | Kuratowski's theorem | |

Beginner | Planar graphs | Equivalents of the 4-color theorem | |

Beginner | Ramsey theory | Ramsey's theorem | |

Intermediate | Structure of 1-, 2-, 3-connected graphs | Blocks | |

Intermediate | Structure of 1-, 2-, 3-connected graphs | Ear-decomposition | |

Intermediate | Structure of 1-, 2-, 3-connected graphs | Contractible edges | |

Intermediate | Perfect graphs | Bipartite graphs | |

Intermediate | Perfect graphs | Comparability graphs | |

Intermediate | Tutte's synthesis of 3-connected graphs | Tutte's synthesis of 3-connected graphs | |

Intermediate | Systems of distinct representatives | Systems of distinct representatives | |

Intermediate | Matching polytope | Matching polytope | |

Intermediate | Chinese postman problem | Chinese postman problem | |

Intermediate | Dual graphs | Dual graphs | |

Intermediate | Graphs on surfaces | Graphs on surfaces | |

Intermediate | Highly chromatic graphs of large girth | Highly chromatic graphs of large girth | |

Intermediate | Vizing's theorem | Vizing's theorem | |

Intermediate | Erdos-de Bruijn compactness theorem | Erdos-de Bruijn compactness theorem | |

Advanced | Line graphs of bipartite graphs | Line graphs of bipartite graphs | |

Advanced | Chordal graphs | Chordal graphs | |

Advanced | Complements of the above | Complements of the above | |

Advanced | Perfect Graph Theorem | Perfect Graph Theorem | |

Advanced | Dilworth's theorem | Dilworth's theorem | |

Advanced | Applications of Ramsey's theorem | Applications of Ramsey's theorem | |

Advanced | Lower bound for Ramsey numbers | Lower bound for Ramsey numbers | |

Advanced | Properties of random graphs | Properties of random graphs | |

Advanced | Threshold functions | Threshold functions | |

Advanced | 0-1 law | 0-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:

COMS W4203: Introduction to Graph Theory (taught by Timothy Sun at Columbia University)

MATH 6014: Graph Theory (taught at Georgia Institute of Technology)

MATH 4022: Introduction to Graph Theory (taught at Georgia Institute of Technology)

Zelko, Jacob. *Achieving an Undergraduate Level Understanding of Graph Theory*. https://jacobzelko.com/01012023000122-graph-theory-learning. 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.