1 Fundamental concepts

Graph theory studies abstract structures called graphs. A graph represents relationships between objects by using vertices and edges. The subject provides a language for describing networks, pairwise connections, and combinatorial patterns. Its ideas appear throughout mathematics and in many applied fields, including computing, chemistry, and communications.

1.1 Graphs and their components

A graph is formed from a set of vertices together with a set of edges joining selected pairs of vertices. The structure may be finite or infinite, and the way the edges connect the vertices determines many of the graph’s basic properties. Graphs can be drawn as diagrams, but their study is primarily abstract and does not depend on a particular picture.

1.1.1 Vertices and edges

Vertices are the fundamental points of a graph, while edges are the connections between them. In an undirected graph, an edge has no orientation and simply links two vertices. In a directed graph, an edge has a direction and is often called an arc. Vertices may represent physical objects, states, locations, or other entities, depending on the application.

1.1.2 Incidence and adjacency

Incidence describes which vertices are connected to which edges. Two vertices are adjacent when an edge joins them, and two edges may be considered incident if they share a vertex. These relations form the basis for many graph definitions and algorithms.

1.2 Types of graphs

Graphs are classified by the nature of their edges, allowed repetitions, and size. Different categories are useful for different problems, and a single graph may be examined through several viewpoints. This flexibility is one reason graph theory is so widely applicable.

1.2.1 Directed and undirected graphs

Undirected graphs model symmetric relationships, such as mutual links. Directed graphs model asymmetric relationships, such as one-way streets or ordered pairs. The choice between them affects notions of reachability, degree, and connectivity.

1.2.2 Simple graphs and multigraphs

A simple graph has no loops and no multiple edges between the same pair of vertices. A multigraph may allow several edges between two vertices, and sometimes loops as well. Multigraphs are useful when parallel connections need to be represented explicitly.

1.2.3 Weighted graphs

In a weighted graph, each edge carries a numerical value such as cost, length, capacity, or strength. Weights allow a graph to model optimization problems and quantitative relationships. Many standard algorithms use edge weights to compare routes or connections.

1.2.4 Infinite graphs

Infinite graphs have infinitely many vertices, edges, or both. They arise in parts of combinatorics, logic, and theoretical computer science. Although less common in applications, they reveal structural principles that also inform finite graph theory.

1.3 Basic graph terminology

Graph theory uses a core vocabulary for describing local and global structure. Terms such as degree, subgraph, and isomorphism make it possible to compare graphs and state general results precisely.

1.3.1 Degree of a vertex

The degree of a vertex is the number of edges incident to it, with loops counted according to convention. In directed graphs, one often distinguishes indegree and outdegree. Degree information is central to many structural theorems and counting arguments.

1.3.2 Subgraphs and induced subgraphs

A subgraph is obtained by selecting some vertices and edges from a graph. An induced subgraph is formed by choosing a set of vertices and including every edge of the original graph whose endpoints both lie in that set. Induced subgraphs preserve adjacency relations within the selected vertex set.

1.3.3 Isomorphism

Two graphs are isomorphic if they have the same structure up to relabeling of vertices. An isomorphism preserves adjacency, so the graphs differ only in naming, not in form. Identifying isomorphic graphs is a central theme in graph classification.

2 Paths, walks, and cycles

Paths and cycles describe ways of moving through a graph. These notions capture reachability, route structure, and repeating patterns. They are among the most frequently used concepts in both theoretical and applied graph theory.

2.1 Walks and trails

A walk is a sequence of vertices in which consecutive vertices are adjacent. Walks may repeat vertices and edges unless additional restrictions are imposed. They provide the most general notion of movement through a graph.

2.1.1 Open and closed walks

An open walk begins and ends at different vertices, while a closed walk starts and finishes at the same vertex. Closed walks are important in studying recurrence, cycles, and graph traces. Open walks often model routes from one point to another.

2.1.2 Trails and Eulerian trails

A trail is a walk with no repeated edges. An Eulerian trail is a trail that uses every edge exactly once. Such trails are closely tied to the edge structure of a graph and to classical problems of route planning.

2.2 Paths and shortest paths

Paths are walks with stronger restrictions than general trails. They are used to measure distance, compare routes, and identify efficient connections. Shortest paths play a key role in optimization and network analysis.

2.2.1 Simple paths

A simple path does not repeat vertices. This condition makes the path a clean representation of direct movement through the graph. Simple paths are often used when cycles and backtracking are to be excluded.

2.2.2 Geodesics

A geodesic is a shortest path between two vertices. A graph may contain one geodesic or several geodesics between the same pair of vertices. Geodesics define the graph-theoretic notion of distance.

2.3 Cycles

Cycles are closed paths that return to their starting point. They reveal circular structure and help distinguish trees from more complex graphs. The presence or absence of cycles is often decisive in classification results.

2.3.1 Simple cycles

A simple cycle is a closed path with no repeated vertices other than the first and last. Simple cycles are the basic cyclic building blocks in many graphs. They are important in planarity, coloring, and network structure.

2.3.2 Hamiltonian cycles

A Hamiltonian cycle visits every vertex exactly once before returning to the start. Unlike Eulerian trails, which concern edges, Hamiltonian cycles focus on vertices. Determining whether such a cycle exists can be difficult and is a major topic in combinatorial optimization.

3 Connectivity

Connectivity concerns whether a graph holds together as a single piece or breaks into separate parts. It is a fundamental concept for understanding communication, robustness, and decomposition. Many structural and algorithmic results rely on connectivity properties.

3.1 Connected graphs

A graph is connected if every pair of vertices can be joined by a path. Connectedness indicates that the graph has no isolated substructure separated from the rest. It is one of the most basic global properties of a graph.

3.1.1 Connected components

Connected components are the maximal connected subgraphs of a graph. Each vertex belongs to exactly one component. The decomposition into components partitions the graph into its natural disconnected pieces.

3.1.2 Cut vertices and bridges

A cut vertex is a vertex whose removal increases the number of connected components. A bridge is an edge with the same effect when removed. These elements indicate vulnerability in the structure of a graph.

3.2 Strong connectivity

In directed graphs, connectivity has a directional form. Because edges may only be traversed one way, the relevant notion is whether vertices can reach each other along directed paths. This leads to a richer set of connectivity types than in undirected graphs.

3.2.1 Strongly connected digraphs

A directed graph is strongly connected if every vertex can reach every other vertex by a directed path. Strong connectivity is the directed analogue of connectedness. It is central in the study of communication networks and state transitions.

3.2.2 Weak connectivity

A directed graph is weakly connected if the underlying undirected graph is connected. Weak connectivity ignores edge directions and captures only the presence of a link structure. It is a less restrictive notion than strong connectivity.

3.3 Graph separation

Separation studies how a graph can be split by removing vertices or edges. It provides a measure of resilience and reveals points of structural dependence. Separations are closely related to connectivity thresholds.

3.3.1 Vertex cuts

A vertex cut is a set of vertices whose removal disconnects the graph or separates specified parts of it. Small vertex cuts indicate that the graph can be broken apart easily. Such sets are important in network reliability and decomposition theory.

3.3.2 Edge cuts

An edge cut is a set of edges whose removal disconnects the graph. Edge cuts measure the graph’s edge-based robustness. They are often studied alongside vertex cuts in connectivity theory.

4 Trees and forests

Trees are graphs with no cycles, and forests are collections of trees. These structures are among the simplest and most important in graph theory. They arise in hierarchical modeling, search processes, and spanning constructions.

4.1 Tree structures

A tree is a connected graph without cycles. This combination of properties makes trees highly structured and easy to analyze. Many inductive arguments in graph theory rely on tree properties.

4.1.1 Rooted trees

A rooted tree has one distinguished vertex called the root. The root provides a hierarchy, and the remaining vertices may be viewed by their levels or generations. Rooted trees are common in data structures and combinatorial enumeration.

4.1.2 Spanning trees

A spanning tree of a connected graph is a tree containing all the vertices of the graph. It preserves connectivity while removing cycles. Spanning trees are fundamental in optimization and network design.

4.2 Forests

A forest is a graph with no cycles, possibly disconnected. Every component of a forest is a tree. Forests generalize trees by allowing multiple connected parts.

4.2.1 Spanning forests

A spanning forest is a forest that includes all vertices of a graph. It appears naturally in disconnected graphs, where each component contributes a tree. Spanning forests are useful in decomposition and algorithmic settings.

4.3 Tree properties

Trees satisfy several distinctive properties that distinguish them from other graphs. These properties often admit elegant proofs and serve as useful characterizations. They also make trees central to inductive reasoning.

4.3.1 Leaves and internal vertices

A leaf is a vertex of degree one in a tree, while internal vertices have higher degree. Leaves mark the ends of a tree’s branches. Their presence is used in many proofs about tree structure.

4.3.2 Characterizations of trees

A graph is a tree if and only if it is connected and acyclic. Equivalent characterizations include having exactly one simple path between any two vertices and having one fewer edge than vertices when finite and connected. Such equivalences make trees especially tractable.

5 Planarity and embeddings

Planarity concerns whether a graph can be drawn in the plane without edge crossings. Embeddings describe how a graph is represented on a surface. These ideas connect graph theory with topology and geometric intuition.

5.1 Planar graphs

A planar graph is a graph that can be drawn in the plane so that edges meet only at their endpoints. Planar graphs have special combinatorial constraints and rich structural theory. They are important in both theory and applications such as circuit design.

5.1.1 Plane graphs

A plane graph is a particular drawing of a planar graph in the plane. Different plane drawings of the same planar graph may have different faces and geometric features. The distinction between abstract planar graphs and concrete plane graphs is important.

5.1.2 Graph embeddings

An embedding places a graph on a surface in a way that avoids forbidden intersections. Embeddings can be studied on the plane, sphere, torus, or more general surfaces. The surface chosen affects the graph’s properties and classification.

5.2 Nonplanarity criteria

Nonplanarity criteria identify graphs that cannot be drawn in the plane without crossings. These results give practical tests for determining when planarity fails. They are among the best-known theorems in graph theory.

5.2.1 Kuratowski's theorem

Kuratowski’s theorem states that a finite graph is nonplanar if and only if it contains a subdivision of one of two specific graphs. This theorem provides a structural characterization of planarity. It is a cornerstone of topological graph theory.

5.2.2 Wagner's theorem

Wagner’s theorem characterizes planar graphs in terms of graph minors. It gives an alternative formulation of nonplanarity based on contractions and deletions. The theorem complements Kuratowski’s result.

5.3 Graph coloring of planar graphs

Planarity strongly influences coloring behavior. Planar graphs have special bounds and constraints that do not hold for arbitrary graphs. The study of planar coloring has produced some of the most celebrated results in graph theory.

5.3.1 Four color theorem

The four color theorem states that every planar graph can be colored with at most four colors so that adjacent vertices receive different colors. It is one of the most famous theorems in mathematics. The result has a long history and a proof that relies heavily on computer verification.

6 Graph coloring

Graph coloring assigns labels, or colors, to graph elements under specified restrictions. It is a central topic because it combines combinatorial structure with optimization. Coloring questions occur naturally in scheduling, resource allocation, and map-style partitioning.

6.1 Vertex coloring

Vertex coloring assigns colors to vertices so that adjacent vertices receive different colors. The goal is often to use as few colors as possible. This basic problem leads to many deeper variants and applications.

6.1.1 Chromatic number

The chromatic number is the minimum number of colors needed for a proper vertex coloring. It measures how difficult a graph is to color under adjacency constraints. Computing it can be challenging for general graphs.

6.1.2 Proper colorings

A proper coloring avoids giving the same color to adjacent vertices. Proper colorings are the standard framework for vertex coloring problems. They are used to formalize exclusion constraints in graphs.

6.2 Edge coloring

Edge coloring assigns colors to edges so that incident edges receive different colors. This notion is useful when conflicts arise between adjacent connections rather than between vertices. Edge coloring has its own theory and extremal bounds.

6.2.1 Chromatic index

The chromatic index is the minimum number of colors needed for a proper edge coloring. It depends on the graph’s maximum degree and finer structural features. Edge-coloring theory includes deep results about exact values and bounds.

6.3 Special coloring problems

Beyond standard vertex and edge coloring, graph theory studies several refined coloring models. These variants often encode additional constraints and may be more suitable for applications. They also reveal new combinatorial phenomena.

6.3.1 Total coloring

Total coloring assigns colors to both vertices and edges so that adjacent or incident elements receive different colors. This combines vertex and edge coloring into one framework. It leads to challenging conjectures and partial results.

6.3.2 List coloring

In list coloring, each vertex has a specified list of allowable colors, and the task is to choose a proper coloring from those lists. This generalization captures heterogeneous constraints. It is especially useful in probabilistic and algorithmic settings.

7 Matching and covering

Matchings and coverings describe ways of selecting edges or vertices to meet structural goals. These concepts are closely linked to optimization, network design, and combinatorial existence theorems. They are among the most useful topics in applied graph theory.

7.1 Matchings

A matching is a set of edges no two of which share a vertex. Matchings represent compatible pairings or simultaneous nonconflicting connections. They are fundamental in combinatorial optimization.

7.1.1 Maximum matchings

A maximum matching is a matching with the largest possible number of edges. It need not be unique. Finding maximum matchings is a classical algorithmic problem with efficient solutions in many graph classes.

7.1.2 Perfect matchings

A perfect matching covers every vertex of the graph exactly once. Such matchings exist only in graphs with an even number of vertices and suitable structure. They are important in pairing problems and structural graph theory.

7.2 Covers

A cover is a set of vertices or edges that touches all elements of a specified type. Covers complement matchings in many theoretical and computational results. They are often used to express dualities in graph problems.

7.2.1 Vertex covers

A vertex cover is a set of vertices incident to every edge of the graph. Vertex cover problems ask for small sets that monitor all connections. This is a standard optimization problem in graph theory.

7.2.2 Edge covers

An edge cover is a set of edges such that every vertex is incident to at least one selected edge. Edge covers are closely related to matchings and are often studied together with them. They appear in pairing and selection problems.

7.3 Matching theorems

Matching theorems provide conditions guaranteeing the existence of matchings with desired properties. These results are central to bipartite graphs and more general settings. They also illustrate the interplay between local constraints and global structure.

7.3.1 Hall's theorem

Hall’s theorem gives a criterion for the existence of a matching that covers one side of a bipartite graph. The condition is expressed in terms of neighborhood sizes of subsets. It is one of the most important combinatorial existence theorems.

7.3.2 Tutte's theorem

Tutte’s theorem characterizes when a graph has a perfect matching. It generalizes matching theory beyond bipartite graphs. The theorem is a major result in structural graph theory.

8 Extremal and enumerative graph theory

Extremal graph theory asks how large or dense a graph can be while avoiding a certain property. Enumerative graph theory counts graphs and related structures. Together, these areas study the limits and quantities of graph configurations.

8.1 Extremal problems

Extremal problems seek optimal bounds under specified constraints. They often ask for the maximum number of edges, subgraphs, or other features possible without violating a condition. Such questions are central to combinatorics.

8.1.1 Turán-type results

Turán-type results determine how dense a graph can be while avoiding a complete subgraph or another forbidden configuration. These theorems describe sharp thresholds for certain properties. They are foundational in extremal combinatorics.

8.1.2 Forbidden subgraphs

A forbidden subgraph is a configuration that is excluded from a graph class. Studying graphs that avoid particular subgraphs leads to precise structural and extremal results. This approach is common in classification problems.

8.2 Counting graphs

Counting problems aim to determine how many graphs satisfy given conditions. They may depend on the number of vertices, edges, or additional restrictions. Enumerative techniques include combinatorial identities and analytic tools.

8.2.1 Enumeration by vertices and edges

Graphs can be counted according to the number of vertices and edges they contain. Such enumeration helps organize graph families and estimate their abundance. It also supports asymptotic analysis.

8.2.2 Generating functions

Generating functions encode sequences that count graphs or graph features. They transform combinatorial counting into algebraic or analytic expressions. This method is widely used in enumerative combinatorics.

9 Graph algorithms

Graph algorithms are procedures for solving problems on graphs efficiently. They underlie many practical systems in computing and operations research. Their study combines structural insight with computational complexity.

9.1 Traversal algorithms

Traversal algorithms visit vertices and edges in systematic order. They are often used as building blocks for more advanced methods. Traversals can explore connectivity, search for paths, and construct derived data.

Breadth-first search explores a graph level by level from a starting vertex. It finds shortest paths in unweighted graphs and can identify connected components. Its simplicity and efficiency make it a standard algorithm.

Depth-first search follows one branch as far as possible before backtracking. It is useful for cycle detection, topological reasoning, and component analysis. Many graph algorithms are built on depth-first exploration.

9.2 Optimization algorithms

Optimization algorithms find graphs structures that minimize or maximize a criterion. They are essential in routing, network design, and resource allocation. Several classical graph problems have efficient polynomial-time algorithms.

9.2.1 Minimum spanning trees

A minimum spanning tree connects all vertices of a weighted connected graph with minimum total edge weight. It represents the least expensive way to maintain connectivity. Classic algorithms for this problem are widely used in practice.

9.2.2 Maximum flow

Maximum flow asks for the greatest amount of material that can be sent through a network from a source to a sink subject to capacity constraints. It is a fundamental problem in combinatorial optimization. Flow methods are closely related to cuts and duality.

9.3 Complexity considerations

Not all graph problems admit efficient algorithms. Complexity theory classifies problems by their resource requirements and feasibility. Graph theory provides many of the standard examples used in this classification.

9.3.1 Polynomial-time problems

Polynomial-time problems can be solved in time bounded by a polynomial function of the input size. These problems are generally considered tractable. Many basic graph tasks, including traversal and several optimization problems, fall into this category.

9.3.2 NP-completeness in graph theory

Many graph problems are NP-complete, meaning they are among the hardest problems in NP under standard reductions. Examples include several coloring, Hamiltonian, and covering questions. NP-completeness shows why some graph problems are unlikely to have efficient exact algorithms.

10 Advanced topics

Advanced graph theory extends the subject into linear algebra, probability, topology, and algebra. These areas reveal deeper invariants and powerful methods. They also connect graph theory to neighboring branches of mathematics.

10.1 Spectral graph theory

Spectral graph theory studies graphs using eigenvalues and eigenvectors of associated matrices. It links combinatorial structure with linear algebra. The spectrum of a graph can reveal connectivity, expansion, and other properties.

10.1.1 Adjacency matrices

The adjacency matrix records which vertices are adjacent. Its entries encode the graph in matrix form, allowing algebraic analysis of walks and substructures. Matrix powers count certain types of paths.

10.1.2 Laplacian matrices

The Laplacian matrix combines adjacency and degree information. It plays a major role in studying connectivity, diffusion, and partitioning. Laplacian methods are widely used in both theory and applications.

10.2 Random graphs

Random graphs are graph models generated by probability rules. They are used to study typical behavior rather than individual examples. This perspective helps explain threshold phenomena and large-scale structure.

10.2.1 Erdős–Rényi models

Erdős–Rényi models choose edges randomly according to a fixed rule. They are among the most studied random graph families. These models provide a benchmark for probabilistic graph behavior.

10.2.2 Probabilistic methods

The probabilistic method proves that a graph with certain properties exists by showing that a random construction has positive probability of satisfying them. This technique is powerful in extremal and combinatorial theory. It often yields existence results without explicit examples.

10.3 Topological graph theory

Topological graph theory studies graphs drawn on surfaces and the topological constraints that arise. It combines combinatorics with geometry and surface theory. Questions about embeddings, genus, and minors are central to this field.

10.3.1 Graph genus

The genus of a graph is the minimum genus of a surface on which the graph can be embedded without crossings. It measures how far the graph is from being planar. Lower genus usually indicates simpler embedding behavior.

10.3.2 Graph minors

A graph minor is obtained by deleting edges or vertices and contracting edges. Minor theory provides a powerful way to classify graphs by forbidden configurations. It has become one of the major organizing principles of modern graph theory.

10.4 Algebraic graph theory

Algebraic graph theory studies graphs using algebraic objects such as groups, matrices, and symmetries. It highlights deep relationships between structure and transformation. The approach is especially effective for highly symmetric graphs.

10.4.1 Automorphism groups

The automorphism group of a graph consists of all vertex permutations that preserve adjacency. It measures the graph’s symmetries. Large automorphism groups often indicate a high degree of regularity.

10.4.2 Cayley graphs

Cayley graphs are graphs constructed from groups and generating sets. They provide a visual and combinatorial representation of algebraic structure. These graphs are important in both group theory and network design.