Graph Theory

From basic concepts to spectral and algebraic graph theory

About This Series

Graph theory is the branch of mathematics that studies discrete structures made up of vertices and edges, and is one of the central areas of discrete mathematics. This series starts from the basic concepts of graphs and proceeds step by step through trees, coloring, and matching, network flow, and on to spectral and algebraic graph theory.

Graph theory is applied across a wide range of fields, including computer science, network design, social network analysis, optimization, chemistry, and machine learning (graph neural networks).

Learn by Level

Introductory

High school to first-year university

  • Definition and representation of graphs
  • Degree and the handshaking lemma
  • Paths and cycles
  • Connectivity

Basic

University years 1–2

  • Trees and forests
  • Eulerian and Hamiltonian paths
  • Planar graphs
  • Coloring
  • Matching

Intermediate

University years 3–4

  • Network flow
  • Connectivity (vertex/edge)
  • Ramsey theory
  • Extremal graph theory

Advanced

Graduate level

  • Spectral graph theory
  • Algebraic graph theory
  • Random graphs
  • Graph minors

Learning Path

Learning path for graph theory A flow chart showing the order of study: Introductory (basic concepts) → Basic (trees, coloring, matching) → Intermediate (flow, extremal) → Advanced (spectral, algebraic). At the bottom, four representative graphs are shown: the complete graph K4, a binary tree, the complete bipartite graph K3,2, and the cycle C5. Intro Basic concepts Basic Trees, coloring Interm. Flow, extremal Advanced Spectral, algebraic Intro: definition of a graph, degree, connectivity Basic: trees, Eulerian paths, planar graphs, coloring Interm.: flow, connectivity, Ramsey, extremal Adv.: spectral, minors, random graphs Examples of graphs Complete graph K₄ Binary tree Complete bipartite K₃,₂ Cycle C₅
Figure 1. The learning path and representative graphs (the complete graph K₄, a binary tree, the complete bipartite graph K₃,₂, and the cycle C₅).

Main Topics

Graph Structure

Basic structures such as vertices and edges, degree, connectivity, trees, and cycles.

Coloring Problems

Vertex coloring, edge coloring, the chromatic number, and the four color theorem.

Matching and Flow

Matching in bipartite graphs, and the max-flow min-cut theorem.

Spectral Theory

The adjacency matrix, the Laplacian, and the relationship between eigenvalues and structure.

Frequently Asked Questions

What is graph theory?

Graph theory is the branch of mathematics that studies discrete structures made up of vertices (nodes) and edges, and is one of the central areas of discrete mathematics. It has a wide range of applications, including networks, path problems, and coloring problems, spanning computer science and optimization.

What is the difference between an Eulerian path and a Hamiltonian path?

An Eulerian path traverses every edge of a graph exactly once, whereas a Hamiltonian path visits every vertex exactly once. The existence of an Eulerian path can be decided completely from vertex degrees, but deciding whether a Hamiltonian path exists is an NP-complete problem.

What is the four color theorem?

The four color theorem states that any map drawn in the plane (equivalently, any planar graph) can be colored with just four colors so that adjacent regions receive different colors. It is also famous as the first major theorem proved with extensive use of a computer, by Appel and Haken in 1976.