Graph Theory

Graph Theory or Network Theory is a highly important field within discrete mathematics, and in recent times, it has been expanding its scope with endless applications. Naturally advantageous for visualization and algorithm-friendly, it is closely related to computer science and data science. Ironically, proofs often involve more words than equations, making it a subject that mathematics students sometimes find challenging. Regardless of personal preferences, studying it is never a waste of time, and since there are no particular prerequisites, it can be recommended to undergraduate freshmen without burden.

Basics

• Graphs and Networks
  • Isomorphism
  • Homeomorphism
• Definition of Hypergraph

Spectral

• Matrix Representation of Graphs
• Degree $\deg$
  • Handshake Lemma
  • Handshake Dilemma
• Spectral Distance Between Graphs

Topology

• Set Representation of Graphs
  • Subgraph
• Distance, Neighborhood, Diameter, Girth $d$, $N$, $\text{diam}$, $\text{girth}$
• Graph Complement $\overline{G}$

Deterministic Graphs

Named Graphs

• Null Graph and Complete Graph $K_{n}$
• Regular Graph
• Bipartite Graph $G(A,B)$
• Infinite Graph
  • König’s Theorem
• Erdős–Gallai Theorem
• Havel–Hakimi Algorithm
• Tree Graph
  • Labeled Trees and Cayley’s Theorem
• Integral Graph
  • Anderson–Livingston Theorem
• Perfect Graph

Path Problems

• Walks, Trails, Paths, Cycles
  • Orientation of Graphs
• Euler Graph
  • Seven Bridges of Königsberg Problem and Solution
  • Fleury’s Algorithm
• Hamiltonian Graph
  • Dirac’s Theorem

Four Color Problem

• Planar Graphs and Kuratowski’s Theorem
  • Euler’s Polyhedron Formula
  • Properties of Simple Planar Graphs
• Graph Coloring and Brooks’ Theorem
• k-Connectivity of Graphs and Menger’s Theorem
• Geometric Dual Graphs
• Abstract Dual Graphs
• Definition of Map in Graph Theory
• Five Color Theorem
• Four Color Map Problem

Nondeterministic Networks

Random Networks

• Families and Properties of Graphs $2^{\binom{n}{2}}$, $\mathscr{G}_{n,m}$
• Random Network $\mathbb{G}$
  • Degree Distribution
• Erdős–Rényi Model $\mathbb{G}_{n,m}$
  • Gilbert Model $\mathbb{G}_{n,p}$
• Scale-Free Networks
  • Chung–Lu Fitness Model
  • Barabási–Albert Model
• Euclidean Networks

Centrality

• Hub Nodes
• Degree Centrality
• Betweenness Centrality
  • Stress Centrality
• Closeness Centrality
• Eigenvector Centrality

Practice

• Graph Layouts
• Gephi: Graph Visualization and Analysis Software
• NetworkX: Python Package for Graph Analysis
  • Reading and Writing GEXF Files
• Graphs.jl: Julia Package for Graph Analysis

References

• Albert, Barabási. (2002). Statistical mechanics of complex networks
• Barabási. (2016). Network Science
• Brouwer. (2011). Spectra of Graphs
• Frieze. (2015). Introduction to Random Graphs
• Newman. (2010). Networks: An Introduction
• Wilson. (1970). Introduction to Graph Theory