1. Foundations of Graphs
1.1 Basic definitions: vertices, edges, adjacency
A graph is defined by a set of vertices (nodes) and a set of edges connecting pairs of vertices. When an edge joins two vertices, those vertices are said to be adjacent. Edges may be treated as unordered pairs in undirected graphs or ordered pairs in directed graphs. Graphs abstract away geometric details while retaining the information about which objects are linked to which.
1.2 Representations of graphs
1.2.1 Edge lists and adjacency lists
Common data structures store a graph by listing its edges or by recording, for each vertex, which other vertices it connects to. An edge list is a collection of pairs (or ordered pairs) representing connections. An adjacency list maps each vertex to a list of its neighbors. Adjacency lists are particularly natural for sparse graphs, where the number of edges is relatively small compared with the number of vertices.
1.2.2 Adjacency matrices
An adjacency matrix is a square matrix in which entry \((i,j)\) indicates whether there is an edge between vertex \(i\) and vertex \(j\). For unweighted undirected graphs, the matrix is symmetric; for directed graphs, it need not be. Adjacency matrices provide direct constant-time access to adjacency information but can be memory-intensive for large, sparse graphs.
1.3 Common graph types
1.3.1 Simple graphs and multigraphs
A simple graph typically forbids loops (edges from a vertex to itself) and multiple edges between the same pair of vertices. A multigraph allows repeated edges between the same endpoints; loops may also be permitted depending on the convention. This distinction matters for counting, degrees, and certain algorithmic behaviors, because multiplicity affects how many connections a vertex effectively has.
1.3.2 Directed graphs and undirected graphs
Undirected graphs model relationships with no inherent direction, meaning an edge indicates mutual adjacency. Directed graphs (digraphs) represent one-way relationships; edges have an orientation from a tail vertex to a head vertex. In directed graphs, vertex degrees split into in-degree and out-degree, and many properties depend on the flow of directionality.
2. Graph Properties and Invariants
2.1 Degree and local structure
2.1.1 Degree of a vertex
The degree of a vertex counts how many edges are incident to it. In undirected graphs, each edge contributes to the degree of both of its endpoints. In directed graphs, a vertex may have in-degree and out-degree counting incoming and outgoing edges separately. Degree is a fundamental local measure used in many characterizations and algorithmic heuristics.
2.1.2 Degree sequences
A degree sequence is a list of degrees for all vertices, often sorted into nonincreasing order. Degree sequences capture global constraints derived from local counts: not every list of integers can occur as the degrees of a simple graph. Conditions for realizability link combinatorial structure to arithmetic properties of the sequence.
2.2 Paths, walks, and cycles
2.2.1 Connectivity concepts
A path is a sequence of vertices where consecutive vertices are adjacent, typically without repeating vertices. A walk generalizes this by allowing repetitions. Connectivity describes whether vertices can reach each other via such sequences; for instance, connected graphs have no separation into disconnected parts, while more refined notions distinguish weak and strong connectivity in directed settings.
2.2.2 Cycle properties
A cycle is a closed path with no repeated vertices except for the starting/ending vertex. Cycles are central to understanding redundancy and feedback-like structure in networks. Even when a graph is not fully connected, cycles may appear in particular components, influencing traversal behavior and coloring constraints.
2.3 Graph invariants
2.3.1 Components, Euler characteristic (informal overview)
Graph components partition a graph into maximal connected subgraphs. Various invariants can be derived from these components, such as the number of connected components. In a more geometric or topological perspective, the Euler characteristic relates vertices, edges, and faces in planar drawings; in graph-theoretic terms it often appears through formulas that compare these counts, though details depend on the embedding context.
2.3.2 Chromatic number and basic coloring invariants
The chromatic number is the smallest number of colors needed to produce a proper vertex coloring, where adjacent vertices do not share a color. It serves as a graph invariant because it depends only on adjacency structure, not on how the graph is drawn. As with other invariants, it provides a compact summary of constraint tightness.
3. Special Classes of Graphs
3.1 Bipartite graphs
3.1.1 Characterization and basic tests
A bipartite graph has its vertices divided into two sets such that every edge joins a vertex from one set to the other, never within the same set. A common characterization uses cycle structure: a graph is bipartite exactly when it has no odd-length cycle. In algorithmic settings, bipartiteness can be tested by attempting a consistent two-set assignment via breadth-first exploration.
3.2 Trees and forests
3.2.1 Rooted vs. unrooted trees
A tree is a connected acyclic graph. A rooted tree designates one vertex as the root, turning the structure into a parent-child hierarchy. Rooting does not change the underlying edges, but it clarifies orientation for descriptions such as subtree relationships and recursive reasoning.
3.2.2 Properties of trees
Trees satisfy several equivalent characterizations relating edges, vertices, and cycles. A key feature is that between any two vertices there is exactly one simple path. This uniqueness simplifies many computations, from dynamic programming on tree structures to proofs about acyclicity.
3.3 Complete graphs and regular graphs
3.3.1 Complete graphs
A complete graph contains an edge between every pair of distinct vertices. Because of this maximal adjacency, complete graphs are useful test cases for extremes: they require many colors under vertex coloring rules and have highly symmetric structure useful for intuition and formal arguments.
3.3.2 Regularity and consequences
A regular graph is one where every vertex has the same degree (or, in directed variants, the same in-degree and out-degree pattern depending on definition). Regularity imposes uniform local structure, often implying stronger global symmetry and enabling simplified analyses of algorithms, spectra-related properties, and counting arguments.
4. Graph Algorithms (Discrete Mathematics Focus)
4.1 Traversal algorithms
4.1.1 Breadth-first search (BFS)
Breadth-first search explores a graph in layers based on distance from a starting vertex. Using a queue, BFS visits all neighbors of the starting point, then neighbors at the next distance, and so on. This traversal is often used to compute shortest path lengths in unweighted graphs and to test properties such as bipartiteness.
4.1.2 Depth-first search (DFS)
Depth-first search explores by following a branch as far as possible before backtracking. Using a stack-like discipline (explicit stack or recursion), DFS reveals structural features such as reachable regions, spanning trees, and backtracking-based classifications. DFS is widely used in algorithmic proofs and for decomposition-style tasks.
4.2 Shortest paths
4.2.1 Unweighted shortest paths (conceptual)
In unweighted graphs, shortest paths are measured by number of edges. BFS naturally finds shortest paths from a fixed source to all reachable vertices because it expands frontier layers in increasing distance order. The method also supports reconstructing one shortest route using predecessor pointers.
2.2.2 Weighted shortest paths (high-level)
When edges carry weights that represent cost, distance, or time, shortest paths minimize total weight. Algorithms differ depending on weight assumptions (such as nonnegative weights) and may require priority-based exploration. At a high level, the goal remains the same: efficiently identify paths with minimum cumulative cost.
4.3 Connectivity and spanning structures
4.3.1 Minimum spanning trees (conceptual)
A minimum spanning tree is a spanning tree whose total edge weight is as small as possible. It applies to connected weighted graphs, selecting a subset of edges that preserves connectivity without cycles while optimizing total weight. Conceptually, it reflects a tradeoff between keeping the graph connected and avoiding unnecessary expensive edges.
4.3.2 Spanning trees and spanning forests
A spanning tree is a tree that includes all vertices of the graph. If the graph is disconnected, one considers spanning forests: a collection of spanning trees, one for each connected component. Spanning structures are central because they reduce a graph while retaining reachability information.
5. Matching, Covering, and Pairing Concepts
5.1 Matchings
5.1.1 Definitions and examples
A matching is a set of edges no two of which share a common vertex. This models “pairwise non-overlapping” connections, such as assigning partners without reuse of vertices. Matchings can be small or large depending on the graph’s structure.
5.1.2 Maximum matching ideas
A maximum matching is a matching of largest possible size (maximum number of edges). Finding maximum matchings is a major algorithmic theme, with approaches that build and adjust candidate matchings until optimality is reached. Conceptually, algorithms search for augmenting opportunities that increase the number of matched edges.
5.2 Vertex covers and edge covers
5.2.1 Relationships to matchings
A vertex cover is a set of vertices such that every edge has at least one endpoint in the set. Matchings and vertex covers are closely related: a matching provides a lower bound on the size needed for a vertex cover because each matched edge requires coverage by at least one endpoint. In bipartite graphs, these relationships become particularly tight, enabling strong duality-style statements.
5.2.2 Common approximation and exact approaches (high-level)
Vertex cover and edge cover problems can be solved exactly in various settings (with differing complexity across graph classes) or approximated in general graphs. At a high level, exact methods often rely on problem-specific structure, while approximation techniques balance speed with provable bounds on how close the solution is to optimal.
6. Graph Colorings
6.1 Coloring basics
6.1.1 Proper vertex coloring
A proper vertex coloring assigns a color to each vertex so that adjacent vertices receive different colors. The coloring must respect the graph’s adjacency constraints, turning a structural question into a combinatorial assignment problem.
6.1.2 Chromatic number intuition
The chromatic number measures how many colors are truly necessary under optimal assignment. It ranges from 1 for graphs with no edges up to higher values for dense or constrained graphs. Intuitively, a larger chromatic number signals stronger incompatibility among vertices under the “adjacent must differ” rule.
6.2 Special coloring cases
6.2.1 Bipartite graphs and 2-coloring
Bipartite graphs are exactly those that can be colored using two colors, one for each part. The absence of odd cycles ensures that a consistent two-color assignment can be maintained across the graph, and the existence of an odd cycle would force a conflict with only two colors.
6.2.2 Planar coloring overview (non-controversial, high-level)
For planar graphs—graphs that can be drawn in the plane without edge crossings—vertex coloring has well-studied bounds. At a high level, planar constraints limit the ways vertices and edges can interact, which restricts how many colors may be necessary. The study of planar graph coloring combines combinatorial reasoning with geometric embedding considerations.
7. Planarity and Embeddings (Introductory)
7.1 Graph embeddings
7.1.1 Drawings and crossings
A graph embedding describes how a graph can be drawn on a surface so that edges intersect only under allowed conditions. In the plane, a drawing with no crossings corresponds to a planar embedding. The number and pattern of crossings matter for determining whether a “crossing-free” representation exists.
7.2 Planar graphs
7.2.1 Informal characterization and implications
A planar graph is a graph that can be embedded in the plane without edge crossings. Planarity imposes structural restrictions that influence algorithm design and combinatorial bounds, and it provides a bridge between discrete graph structure and geometric intuition. Many properties and invariants become easier to reason about when a graph’s embedding behavior is controlled.