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

# Bibliography

Not Available

### Motivation

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.

##### Concepts
• 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:

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

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

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

##### Facts
• Definition of a graph and its components:

• Vertices (also called nodes).

• Edges.

• Weights.

• Labels.

• Subgraphs and isomorphism.

• Directed graphs and their representations:

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

• Matrix representations:

• Incidence matrices.

• Graph algorithms:

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

##### Procedures
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:

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

DoneTopicResourcesOutcomes
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
Incidence matrices[1]Incidence matrix concept; representation of incidence graphs
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
AdvancedComplements of the aboveComplements of the above
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

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)

## How To Cite

Zelko, Jacob. Achieving an Undergraduate Level Understanding of Graph Theory. https://jacobzelko.com/01012023000122-graph-theory-learning. December 31 2022.

## References:

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

## Discussion:

CC BY-SA 4.0 Jacob Zelko. Last modified: May 19, 2024. Website built with Franklin.jl and the Julia programming language.