Glossary of graph theory

Graph theory is a branch of discrete mathematics dedicated to the study of graphs, which are abstract mathematical structures composed of a set of vertices (also called nodes) connected by edges to model pairwise relationships between objects.^[1] A glossary of graph theory terms compiles precise definitions for the field's specialized vocabulary, serving as an essential reference for researchers, students, and practitioners by clarifying concepts from basic components like vertices and edges to advanced structures such as directed graphs, multigraphs, and pseudographs.^[1] The origins of graph theory date back to 1736, when Leonhard Euler addressed the Seven Bridges of Königsberg problem by demonstrating that no Eulerian circuit exists for certain configurations, thereby founding the discipline's focus on traversability and connectivity.^[2] Throughout the 19th and 20th centuries, the field expanded through contributions from figures like Arthur Cayley, who enumerated trees, and Dénes Kőnig, who advanced matching theory, evolving into a cornerstone of combinatorial mathematics with profound implications for algorithm design and real-world modeling.^[3] This glossary encompasses core topics including paths, cycles, and connectedness for analyzing graph traversal; trees and spanning trees for hierarchical structures; bipartite and planar graphs for embedding and partitioning problems; as well as colorings, matchings, and coverings for optimization and scheduling applications.^[4] These terms underpin seminal results, such as Euler's theorem on traversable graphs and Kuratowski's criterion for planarity, enabling the field's extensive use in computer science for network routing, data structures, and artificial intelligence.^[5]

Fundamental Elements

Vertices, Edges, and Incidence

In graph theory, a vertex, also known as a node or point, is a fundamental unit representing an entity in the structure.^[3] The set of all vertices in a graph is denoted by $V(G)$V(G), and vertices may be isolated, meaning they are not incident to any edges, or of degree one, meaning they are incident to exactly one edge.^[6][7] An edge is a connection between vertices that represents a relationship. In undirected graphs, an edge is an unordered pair of vertices, while in directed graphs, also known as digraphs, edges are directed and called arcs, represented as ordered pairs indicating direction from one vertex to another.^[3][8] Special cases include loops, which are edges connecting a vertex to itself (in directed graphs, an arc from a vertex to itself), and multiple edges, where more than one edge exists between the same pair of vertices (or in the same direction for arcs).^[3] A digon refers to two edges between the same pair of vertices in an undirected graph or two arcs in opposite directions between two vertices in a directed graph.^[9][10] The incidence relation describes how edges connect to vertices: an edge is incident to a vertex if the vertex is an endpoint of the edge, and the full incidence is captured by a function $\psi_G(e) = \{u, v\}$ψG​(e)={u,v} for undirected edges or $\psi_G(e) = (u, v)$ψG​(e)=(u,v) for directed arcs, associating each edge $e$e with its endpoints $u$u and $v$v.^[3][11] Two vertices are adjacent if they are connected by an edge (undirected) or an arc (directed from one to the other).^[3] Simple graphs prohibit loops and multiple edges, ensuring each pair of vertices has at most one undirected edge.^[3] In contrast, multigraphs allow multiple edges but no loops, while pseudographs permit both loops and multiple edges, providing more general structures for modeling complex relations.^[3] Examples include the empty graph, which has a set of vertices but no edges (all vertices isolated), and the null graph, which has neither vertices nor edges.^[12][13]

Graphs, Digraphs, and Variants

In graph theory, a graph $G = (V, E)$G=(V,E) is formally defined as an ordered pair consisting of a finite set $V$V of vertices and a set $E$E of unordered pairs of distinct vertices called edges, where each edge connects exactly two vertices and no loops or multiple edges between the same pair are permitted; such graphs are known as simple undirected graphs.^[1] The order of a graph is the number of vertices $|V|$∣V∣, while the size is the number of edges $|E|$∣E∣.^[14] For example, the complete graph $K_n$Kn​ is a simple graph of order $n$n with size $\binom{n}{2}$(2n​), where every pair of distinct vertices is connected by a unique edge.^[1] In contrast, the empty graph (also called the edgeless graph) on $n$n vertices has order $n$n and size 0, with no edges present.^[5] A directed graph, or digraph, extends the notion of a graph by assigning a direction to each edge, represented as an ordered pair $(u, v)$(u,v) indicating an arc from vertex $u$u to $v$v; thus, a digraph $D = (V, A)$D=(V,A) has a set $A$A of such arcs, allowing for possible asymmetry where $(u, v)$(u,v) may exist without $(v, u)$(v,u).^[15] An orientation of an undirected graph is obtained by directing each edge in one of two possible ways, and a tournament is a specific digraph that is a complete orientation of $K_n$Kn​, where exactly one directed edge exists between every pair of distinct vertices.^[16] Graph variants generalize these structures to model more complex relations. A multigraph allows multiple edges between the same pair of vertices but no loops, while a pseudograph permits both multiple edges and loops (edges from a vertex to itself).^[17] A hypergraph replaces edges with hyperedges, which are arbitrary finite subsets of vertices allowing connections among more than two vertices, formally $H = (V, \mathcal{E})$H=(V,E) where $\mathcal{E}$E is a family of subsets of $V$V.^[18] A functional graph is a digraph where each vertex has out-degree exactly 1, arising naturally from the directed graph of a function $f: V \to V$f:V→V with arcs $(v, f(v))$(v,f(v)).^[19] Weighted graphs assign a real number weight to each edge via a function $w: E \to \mathbb{R}$w:E→R, often representing distances, costs, or capacities; unweighted graphs are the special case where all weights are 1 or ignored.^[1] Labeled graphs include distinct labels (e.g., integers or symbols) on vertices, edges, or both to encode additional information, whereas unlabeled graphs are considered up to isomorphism without such distinctions.^[20] An illustrative example is the complete bipartite graph $K_{m,n}$Km,n​, a simple bipartite graph with partite sets of sizes $m$m and $n$n where every vertex in one set connects to every vertex in the other, yielding size $m n$mn.^[21]

Paths and Connectivity

Walks, Trails, Paths, and Cycles

In graph theory, walks, trails, paths, and cycles are fundamental concepts that describe sequences of vertices and edges, enabling the analysis of connectivity and structure within graphs. These terms form a hierarchy based on restrictions on repetitions of vertices and edges, with walks being the most general and cycles the most restrictive closed form. They apply to both undirected graphs and directed graphs (digraphs), where directions impose additional constraints on traversals. Understanding these distinctions is essential for studying properties like connectivity, shortest routes, and Hamiltonian structures. A walk is an alternating sequence of vertices and edges in a graph, beginning and ending with vertices, such that each edge is incident to the vertices immediately preceding and following it in the sequence; walks permit repetitions of both vertices and edges. The length of a walk is the number of edges in the sequence, counted with multiplicity if repetitions occur. For example, in a simple graph with vertices $a, b, c$a,b,c and edges between them, the sequence $a - b - a - c$a−b−a−c is a walk of length 3 that repeats vertex $a$a. A trail is a walk in which no edge is repeated, though vertices may be repeated. Trails are useful for examining edge-disjoint traversals without the stricter vertex constraints. A closed trail, starting and ending at the same vertex, is known as a circuit. The length of a trail or circuit is the number of distinct edges it contains. A path is a trail in which no vertex is repeated, except possibly the starting and ending vertices in closed cases; thus, paths are also known as simple paths due to their lack of repetitions. In digraphs, a directed path (or dipath) follows the same rules but respects edge directions. The length of a path is the number of edges it traverses. A notable example is a Hamiltonian path, which visits every vertex of the graph exactly once; if closed, it forms a Hamiltonian cycle. A geodesic (or shortest path) between two vertices is a path of minimal length connecting them, often used to define graph distances. A cycle is a closed path of at least three vertices where no vertices are repeated except the initial and final ones, which coincide. The circumference of a graph is the length of its longest cycle. A chord of a cycle is an edge connecting two non-consecutive vertices on the cycle, which can divide the cycle into smaller substructures. For infinite graphs, a ray is a one-way infinite path, starting at a vertex and extending indefinitely without repeating vertices, providing a basis for studying ends and unbounded connectivity in infinite structures.

Degrees, Neighborhoods, and Distance Metrics

In graph theory, the degree of a vertex $v$v in an undirected graph $G = (V, E)$G=(V,E) is the number of edges incident to $v$v, denoted $\deg(v)$deg(v).^[22] For a directed graph (digraph), the in-degree of $v$v is the number of edges directed toward $v$v, and the out-degree is the number directed away from $v$v; the total degree is their sum.^[23] The minimum degree $\delta(G)$δ(G) is the smallest $\deg(v)$deg(v) over all $v \in V$v∈V, and the maximum degree $\Delta(G)$Δ(G) is the largest.^[22] A graph is $r$r-regular if every vertex has degree exactly $r$r.^[24] The neighborhood of a vertex $v$v captures its immediate connections. The open neighborhood $N(v)$N(v) is the set of vertices adjacent to $v$v, excluding $v$v itself, so $|N(v)| = \deg(v)$∣N(v)∣=deg(v).) The closed neighborhood $N$N includes $v$v, thus $N = N(v) \cup \{v\}$N=N(v)∪{v}.^[25] In digraphs, the out-neighborhood consists of vertices reachable by outgoing edges from $v$v, while the in-neighborhood uses incoming edges.^[26] Distance metrics quantify separation between vertices based on path lengths. The graph distance $d(u, v)$d(u,v) between vertices $u$u and $v$v in a connected graph is the length (number of edges) of the shortest path from $u$u to $v$v.^[27] The eccentricity of $v$v is $\mathrm{ecc}(v) = \max_{u \in V} d(u, v)$ecc(v)=maxu∈V​d(u,v), the greatest distance from $v$v to any other vertex.^[28] The radius $r(G)$r(G) is the minimum eccentricity over all vertices, $\min_{v \in V} \mathrm{ecc}(v)$minv∈V​ecc(v), and the diameter $D(G)$D(G) is the maximum, $\max_{u,v \in V} d(u, v)$maxu,v∈V​d(u,v).^[29] The isoperimetric number $i(G)$i(G) measures expansion properties tied to neighborhoods, defined as $$i(G) = \min_{\emptyset \neq X \subseteq V, |X| \leq |V|/2} \frac{|\partial X|}{|X|},$$i(G)=∅=X⊆V,∣X∣≤∣V∣/2min​∣X∣∣∂X∣​, where $\partial X$∂X is the edge boundary of $X$X, the number of edges from $X$X to $V \setminus X$V∖X.^[30] Larger $i(G)$i(G) indicates better connectivity from small neighborhoods to the rest of the graph. Moore graphs exemplify optimal distance bounds for given degree and diameter. A Moore graph of degree $\Delta > 2$Δ>2 and diameter $D$D achieves the Moore bound on the number of vertices, $n \leq 1 + \Delta \sum_{i=0}^{D-1} (\Delta - 1)^i$n≤1+Δ∑i=0D−1​(Δ−1)i, realizing the maximum possible size for those parameters.^[31] Known examples include the Petersen graph ($\Delta=3$Δ=3, $D=2$D=2, $n=10$n=10) and the Hoffman-Singleton graph ($\Delta=7$Δ=7, $D=2$D=2, $n=50$n=50).^[32]

Structural Properties

Components, Cuts, and Bridges

In graph theory, a connected component of an undirected graph is a maximal subgraph that is connected, meaning no larger connected subgraph contains it.^[33] These components partition the graph's vertices, and the number of such components measures the graph's overall disconnection.^[33] In directed graphs, a weakly connected component is a maximal subgraph where the underlying undirected graph is connected, ignoring edge directions.^[34] A strongly connected component, by contrast, is a maximal subgraph where every pair of vertices has directed paths in both directions.^[35] An articulation point, also known as a cut vertex, is a vertex whose removal increases the number of connected components in the graph.^[36] Such a vertex lies in multiple connected components after deletion and serves as a critical connection point.^[36] Similarly, a bridge, or cut edge, is an edge whose removal disconnects the graph by increasing the number of connected components.^[37] Bridges are edges not contained in any cycle, representing single points of failure in connectivity.^[37] A block, or biconnected component, is a maximal subgraph without articulation points, meaning it remains connected after removing any single vertex.^[38] In a loopless graph, blocks consist of isolated vertices, bridges, or maximal 2-connected subgraphs, and the graph's block structure forms a tree-like decomposition via the block-cut tree.^[38] Blocks with more than two vertices are inherently 2-connected, ensuring no single vertex removal disconnects them.^[38] A vertex cut, or cut-set, is a set of vertices whose removal disconnects a connected graph into at least two components.^[39] The vertex connectivity $\kappa(G)$κ(G) is the size of the smallest such vertex cut.^[40] An edge cut is a set of edges whose removal disconnects the graph, and the edge connectivity $\lambda(G)$λ(G) is the size of the smallest edge cut, satisfying $\kappa(G) \leq \lambda(G)$κ(G)≤λ(G).^[40] These measures quantify the graph's robustness against vertex or edge failures.^[41] Edge contraction merges two adjacent vertices into one, removing the edge between them while preserving all other incident edges, potentially creating multiedges.^[42] This operation reduces the graph's size while maintaining structural properties in minors and connectivity analyses.^[42] A 2-connected graph admits an ear decomposition: a partition into a cycle followed by paths (ears) where each ear's endpoints lie on the previous subgraph, and internal vertices are new.^[43] This decomposition characterizes 2-connectivity, as every 2-connected graph has such a structure, and every cycle therein initiates some decomposition.^[43] Cactus graphs exemplify structures where blocks are cycles or edges, forming a connected graph with no shared edges between cycles and at most one shared vertex per pair of cycles.^[44] These graphs are planar and arise as block graphs composed solely of cycles connected at articulation points.^[44]

Diameter, Radius, and Eccentricity

In graph theory, the eccentricity of a vertex $v$v in a connected graph $G = (V, E)$G=(V,E) is defined as the maximum distance from $v$v to any other vertex in $V$V, formally $e(v) = \max_{u \in V} d(u, v)$e(v)=maxu∈V​d(u,v), where $d(u, v)$d(u,v) denotes the shortest path distance between $u$u and $v$v.^[28] This measure quantifies how far $v$v is from the most remote vertex in the graph. The radius $r(G)$r(G) of $G$G is the minimum eccentricity among all vertices, $r(G) = \min_{v \in V} e(v)$r(G)=minv∈V​e(v), and the center of $G$G consists of all vertices achieving this minimum value, representing the most central points in terms of distance.^[45] These central vertices minimize the maximum distance to any other vertex, making the center useful for identifying graph cores in applications like network design. The diameter $D(G)$D(G) of a connected graph $G$G is the maximum eccentricity over all vertices, $D(G) = \max_{v \in V} e(v)$D(G)=maxv∈V​e(v), which equivalently captures the longest shortest path between any pair of vertices in $G$G. This graph-level parameter indicates the overall "spread" or extent of the graph. The periphery of $G$G is the set of vertices with eccentricity equal to the diameter, forming the subgraph induced by these extremal vertices, which lie at the graph's boundaries.^[46] In trees, the radius and diameter are related by the inequality $D(G) \leq 2r(G)$D(G)≤2r(G), reflecting the linear structure where paths cannot loop back to extend distances beyond twice the central reach.^[47] In trees, the centroid serves as a balanced separator: it is the vertex (or pair of adjacent vertices) whose removal partitions the tree into components each containing at most half the total number of vertices, minimizing the size of the largest remaining subtree.^[48] This property ensures the centroid acts as an equitable division point, distinct from the center which focuses on distance extremes. An illustrative example is a geodetic graph, where every pair of vertices has exactly one shortest path (geodesic) between them, ensuring unique distances and simplifying eccentricity computations, as seen in trees and complete graphs.^[49]

Special Graph Classes

Trees, Forests, and Acyclic Structures

In graph theory, a tree is an undirected graph that is connected and acyclic, meaning it contains no cycles and there is exactly one path between any pair of distinct vertices.^[50] Equivalently, a tree with $n$n vertices has exactly $n-1$n−1 edges, making it minimally connected while maximizing acyclicity.^[50] Trees serve as fundamental hierarchical structures in graph theory, often modeling branching processes or networks without loops.^[51] A forest is an undirected acyclic graph, which may be disconnected and consists of one or more connected components, each being a tree.^[50] In a forest with $k$k components and $n$n vertices, the number of edges is $n - k$n−k.^[51] Forests generalize trees to allow multiple disjoint structures, useful in representing collections of independent hierarchies. An acyclic graph lacks cycles; for undirected graphs, this equates to a forest, while for directed graphs, a directed acyclic graph (DAG) has no directed cycles, enabling topological ordering of vertices.^[50] In a rooted tree, a designated root vertex imposes a hierarchy, with edges oriented away from the root, defining parent-child relationships where each non-root vertex has exactly one parent.^[51] Leaves are vertices with no children, the depth of a vertex is its distance from the root, and the height of the tree is the maximum depth.^[51] An arborescence is a directed tree rooted at a vertex $r$r, where every other vertex is reachable from $r$r via a unique directed path, with all edges pointing away from the root.^[50] A polytree is a DAG whose underlying undirected graph is a tree, allowing multiple parents per vertex but preserving tree-like connectivity when directions are ignored.^[50] Examples include the spanning tree, a subgraph of a connected graph that is a tree containing all vertices and thus $n-1$n−1 edges.^[52] Another is the caterpillar tree, a tree where all vertices are within distance 1 of a central path (the spine), obtained by attaching leaves to a path.^[53]

Bipartite, Complete, and Regular Graphs

A bipartite graph is an undirected graph whose vertices can be partitioned into two disjoint independent sets such that every edge connects a vertex from one set to a vertex from the other set.^[54] This bipartition ensures that no edges exist within either set, making the graph 2-colorable where adjacent vertices receive different colors.^[55] Equivalently, a graph is bipartite if and only if it contains no odd-length cycles.^[54] The complete bipartite graph $K_{m,n}$Km,n​ is a bipartite graph with partition sets of sizes $m$m and $n$n where every vertex in one set is adjacent to every vertex in the other set, resulting in $m \times n$m×n edges.^[56] This structure maximizes the number of edges possible in a bipartite graph with given partition sizes, serving as a benchmark for extremal problems in bipartite graphs.^[56] A complete graph $K_n$Kn​ is an undirected simple graph on $n$n vertices where every pair of distinct vertices is connected by a unique edge, yielding $\binom{n}{2}$(2n​) edges.^[57] A clique in a graph is a complete subgraph, meaning an induced subgraph that is itself a complete graph.^[58] A regular graph is an undirected graph where every vertex has the same degree $r$r, denoted as an $r$r-regular graph.^[24] In the context of bipartite graphs, a biregular graph (or semiregular bipartite graph) has two partition sets where all vertices in one set have degree $r$r and all in the other have degree $s$s, with $r \neq s$r=s possible.^[59] The Zarankiewicz problem seeks the maximum number of edges in an $m$m-by-$n$n bipartite graph without a complete bipartite subgraph $K_{s,t}$Ks,t​, providing bounds on the density of bipartite graphs avoiding certain substructures.^[60] For instance, the extremal function $z(m,n;s,t)$z(m,n;s,t) upper-bounds the edge count in such graphs.^[60] An example of a bipartite graph is the crown graph $H_{n,n}$Hn,n​, formed by removing a perfect matching from the complete bipartite graph $K_{n,n}$Kn,n​, resulting in a graph where each vertex in one partition connects to all but one vertex in the other.^[61] This construction highlights variations in bipartite edge distributions while preserving bipartiteness.^[62]

Coloring and Partitioning

Cliques, Independent Sets, and Chromatic Concepts

In graph theory, a clique is a subset of vertices in an undirected graph such that every pair of distinct vertices in the subset is connected by an edge, forming a complete subgraph.^[58] A maximal clique is a clique that cannot be extended by adding another vertex while preserving the complete subgraph property, meaning no larger clique contains it.^[63] The clique number $\omega(G)$ω(G) of a graph $G$G is the cardinality of the largest clique in $G$G, providing a measure of the graph's maximum density in terms of complete subgraphs.^[64] An independent set, also known as an anticlique, is a subset of vertices with no edges between any pair of them, representing a sparse induced subgraph.^[65] A maximal independent set is one that cannot be enlarged without violating the independence condition. The independence number $\alpha(G)$α(G) is the size of the largest independent set in $G$G.^[66] Notably, the independence number of $G$G equals the clique number of its complement graph $\overline{G}$G, i.e., $\alpha(G) = \omega(\overline{G})$α(G)=ω(G).^[66] The chromatic number $\chi(G)$χ(G) of a graph $G$G is the smallest number of colors needed to assign to the vertices such that no two adjacent vertices share the same color, known as a proper vertex coloring.^[67] A fundamental inequality states that $\chi(G) \geq \omega(G)$χ(G)≥ω(G), since each vertex in a maximum clique must receive a distinct color in any proper coloring.^[68] Equality holds in certain graph classes, but in general, $\chi(G)$χ(G) can exceed $\omega(G)$ω(G), highlighting the challenge of coloring beyond clique constraints. A graph $G$G is perfect if, for every induced subgraph $H$H of $G$G, the chromatic number equals the clique number, i.e., $\chi(H) = \omega(H)$χ(H)=ω(H).^[69] Perfect graphs form a significant class where coloring complexity aligns perfectly with clique structure, and the Strong Perfect Graph Theorem characterizes them as those without induced odd cycles of length at least 5 (odd holes) or their complements (odd antiholes).^[70] Hole-free graphs, or chordal graphs, are those without induced cycles of length 4 or more, and they are perfect, allowing polynomial-time computation of chromatic numbers via clique trees.^[70] Claw-free graphs exclude the claw $K_{1,3}$K1,3​ (a star with three leaves) as an induced subgraph and include subclasses like line graphs that are perfect, though the full class admits efficient coloring algorithms under additional constraints.^[71] These forbidden-subgraph conditions often simplify the study of cliques and independent sets in dense or structured graphs.^[72] A prominent example illustrating the gap between chromatic and clique numbers is the Grötzsch graph, a triangle-free graph (so $\omega(G) = 2$ω(G)=2) with 11 vertices that requires 4 colors for a proper coloring, thus $\chi(G) = 4$χ(G)=4.^[73] This graph, constructed via the Mycielski construction applied to the 5-cycle $C_5$C5​, serves as the smallest known triangle-free 4-chromatic graph and underscores the existence of graphs where coloring demands exceed clique sizes.^[73]

Matchings, Factors, and Coverings

In graph theory, a matching is a set of edges in a graph without common vertices.^[74] The size of a matching is the number of edges it contains, and a maximum matching is one of largest possible size in the graph.^[75] A perfect matching, also called a 1-factor, is a matching that covers every vertex in the graph, requiring the graph to have an even number of vertices.^[74] An important characterization of maximum matchings involves augmenting paths. Relative to a matching $M$M, an augmenting path is an alternating path (with edges alternating between those in $M$M and not in $M$M) that starts and ends at unsaturated vertices (vertices not incident to any edge in $M$M). Berge's lemma states that a matching $M$M is maximum if and only if the graph contains no $M$M-augmenting path.^[74] For example, in a path graph with three edges, the single middle edge forms a matching of size 1, but an augmenting path using the outer edges allows extension to a matching of size 2, which is maximum.^[74] A factor of a graph is a spanning subgraph (including all vertices) that is regular, meaning every vertex has the same degree $k$k in the subgraph; such a subgraph is a k-factor.^[76] In particular, a 1-factor is a perfect matching, and the existence of k-factors relates to the overall degree structure of the graph, as characterized by Tutte's theorem on factors.^[76] A vertex cover is a set of vertices that includes at least one endpoint of every edge in the graph, and the minimum vertex cover is the smallest such set.^[77] Dually, an edge cover is a set of edges such that every vertex is incident to at least one edge in the set, and the minimum edge cover is the smallest such set (defined only for graphs without isolated vertices).^[77] Gallai identities relate these concepts: for a graph without isolated vertices, the size of a maximum matching plus the size of a minimum edge cover equals the number of vertices, and the size of a minimum vertex cover plus the size of a maximum independent set equals the number of vertices.^[77] In bipartite graphs, König's theorem establishes that the size of a maximum matching equals the size of a minimum vertex cover.^[78] This minimax equality enables efficient algorithms for both problems via maximum flow reductions.^[78] For general graphs, the Gallai-Edmonds decomposition partitions the vertices into three sets: $D$D, the vertices not covered by some maximum matching; $A$A, the vertices adjacent to $D$D; and $C$C, the remaining vertices.^[79] This structure reveals that maximum matchings consist of perfect matchings within components of $C$C, near-perfect matchings in components of $D$D, and edges from $A$A to $D$D, providing a canonical description of the matching theory of the graph.^[79]

Embeddings and Planarity

Planar Graphs and Embeddings

A planar graph is a graph that can be embedded in the Euclidean plane such that no two edges intersect except at their common endpoints (vertices).^[80] Such an embedding divides the plane into connected regions called faces, where each face is bounded by a cycle of edges, and the unbounded outer region is the exterior face.^[81] An embedding of a planar graph specifies the positions of vertices and the paths of edges in the plane. A combinatorial embedding abstracts this by defining, for each vertex, the cyclic order of incident edges around it, which determines the facial cycles without reference to geometric positions.^[82] In contrast, a straight-line embedding represents each edge as a straight-line segment between vertices, preserving planarity; by Fáry's theorem, every simple planar graph admits such an embedding.^[83] For a connected planar graph with $|V|$∣V∣ vertices, $|E|$∣E∣ edges, and $|F|$∣F∣ faces (including the exterior face), Euler's formula states that $$|V| - |E| + |F| = 2.$$∣V∣−∣E∣+∣F∣=2. This relation holds for any planar embedding and provides a fundamental structural constraint on planar graphs.^[84] A graph is non-planar if and only if it contains a subdivision of the complete graph $K_5$K5​ (five vertices all connected) or the complete bipartite graph $K_{3,3}$K3,3​ (two sets of three vertices with all cross edges) as a subgraph; this is Kuratowski's theorem.^[85] For example, the Petersen graph, with ten vertices and fifteen edges forming an outer pentagon, inner star, and connecting edges, is non-planar because it contains a subdivision of $K_{3,3}$K3,3​.^[86]

Outerplanar and Series-Parallel Graphs

An outerplanar graph is a planar graph that admits a planar embedding in which all vertices lie on the boundary of the outer face.^[87] This embedding ensures that the graph can be drawn without edge crossings such that no internal faces enclose vertices not on the exterior boundary.^[88] Outerplanar graphs form a minor-closed family, characterized by the absence of $K_4$K4​ and $K_{2,3}$K2,3​ as minors, meaning that deleting vertices, deleting edges, or contracting edges preserves the property.^[89] Maximal outerplanar graphs are those to which no additional edges can be added while maintaining outerplanarity; they are triangulations where every internal face is a triangle, and all vertices remain on the outer face.^[90] In such graphs, the dual graph—obtained by placing a vertex in each face and connecting them if faces share an edge—forms a tree where every internal vertex has degree exactly 3 after suppressing degree-2 vertices.^[91] A classic example of an outerplanar graph is the fan graph, which consists of a central vertex connected to all vertices of a path graph; this structure embeds with all vertices on the outer face and exemplifies the subclass's simplicity.^[92] Series-parallel graphs, also known as two-terminal series-parallel graphs, are constructed recursively starting from a single edge (with designated source and sink vertices) and applying two operations: series composition, which identifies the sink of one graph with the source of another, and parallel composition, which identifies the sources and sinks of two graphs pairwise.^[93] These graphs are minor-closed, forbidden by the $K_4$K4​ minor, and capture structures arising in network flows and circuit designs due to their recursive build-up from basic components.^[94] Notably, every outerplanar graph is series-parallel, as its embedding allows decomposition into series and parallel substructures without $K_4$K4​ minors, though the converse does not hold since some series-parallel graphs, like certain subdivisions of $K_4$K4​ minus an edge, are not outerplanar.^[95]

Advanced Structural Parameters

Treewidth, Pathwidth, and Decompositions

In graph theory, a tree decomposition of an undirected graph $G = (V, E)$G=(V,E) is a pair $(T, \{X_t\}_{t \in V(T)})$(T,{Xt​}t∈V(T)​), where $T$T is a tree with vertex set $V(T)$V(T) and each $X_t \subseteq V$Xt​⊆V is called a bag, satisfying three properties: (1) every vertex $v \in V$v∈V belongs to at least one bag $X_t$Xt​; (2) every edge $uv \in E$uv∈E has both endpoints in some bag $X_t$Xt​; and (3) for every vertex $v \in V$v∈V, the subgraph of $T$T induced by $\{t \in V(T) \mid v \in X_t\}${t∈V(T)∣v∈Xt​} is connected (a subtree). The width of a tree decomposition is the maximum size of any bag minus one, i.e., $\max_{t \in V(T)} (|X_t| - 1)$maxt∈V(T)​(∣Xt​∣−1). The treewidth of $G$G, denoted $\mathrm{tw}(G)$tw(G), is the minimum width over all possible tree decompositions of $G$G. This parameter quantifies how "tree-like" a graph is, with lower values indicating structures closer to trees. A path decomposition is a special case of a tree decomposition where the underlying tree $T$T is a path.^[96] The pathwidth of $G$G, denoted $\mathrm{pw}(G)$pw(G), is defined analogously as the minimum width over all path decompositions of $G$G.^[96] Pathwidth provides a stricter measure of linearity in graph structure compared to treewidth, as every path decomposition is a tree decomposition but not vice versa, implying $\mathrm{pw}(G) \geq \mathrm{tw}(G)$pw(G)≥tw(G) for any graph $G$G.^[96] For specific graph classes, treewidth takes on characteristic values that highlight its utility. Trees and forests have treewidth 1, as they admit decompositions with bags of size at most 2 (e.g., each edge covered by a bag containing its endpoints). In contrast, the complete graph $K_n$Kn​ has treewidth $n-1$n−1, since any bag covering all edges must include all $n$n vertices. Chordal graphs, which are graphs without induced cycles of length four or more, admit a characterization as precisely the intersection graphs of subtrees of a tree: each vertex corresponds to a subtree, and edges exist between vertices whose subtrees intersect. For chordal graphs, a clique tree serves as an exemplary tree decomposition, where the bags are the maximal cliques of the graph, and the tree structure ensures the intersection properties hold for the subtrees induced by each clique.^[97] This representation underscores the tight connection between chordal structure and tree decompositions of minimal width equal to the size of the largest maximal clique minus one.^[97]

Bandwidth, Branchwidth, and Width Measures

In graph theory, width measures such as bandwidth, branchwidth, and carving-width quantify the structural complexity of graphs by assessing how efficiently they can be decomposed or arranged while controlling the size of certain cuts or separations. These parameters are particularly useful in algorithmic graph theory for bounding the time complexity of dynamic programming approaches to problems like satisfiability or subgraph isomorphism, as they relate to the minimum "congestion" in linear or tree-like layouts of the graph. Unlike treewidth, which relies on vertex-bag decompositions, these measures emphasize edge-based or separation-based decompositions, providing alternative perspectives on graph connectivity that are especially tractable for planar graphs.^[98] Bandwidth, introduced in the context of optimal vertex labelings for minimizing maximum edge stretches, is defined for a graph $G = (V, E)$G=(V,E) with $n = |V|$n=∣V∣ vertices as the minimum value of $\max_{uv \in E} |f(u) - f(v)|$maxuv∈E​∣f(u)−f(v)∣, taken over all bijections $f: V \to \{1, 2, \dots, n\}$f:V→{1,2,…,n}. This corresponds to arranging vertices along a line such that adjacent vertices are as close as possible in the ordering, with the bandwidth representing the maximum deviation for any edge. Computing the bandwidth is NP-hard, even for restricted classes like bipartite graphs, highlighting its computational intractability. For example, the bandwidth of the $n \times n$n×n grid graph is exactly $n$n, illustrating how dense local connections force a linear scaling in the parameter for mesh-like structures. Bandwidth relates to pathwidth through vertex orderings, where the bandwidth of a graph equals its proper pathwidth, a variant emphasizing clique constraints in interval representations.^[99] Branchwidth, a connectivity measure analogous to treewidth but based on ternary tree decompositions of edges, was developed to analyze global edge separations in graphs. A branch-decomposition of a graph $G$G with $m$m edges is a ternary tree $T$T where leaves are labeled by the edges of $G$G, and for each internal edge of $T$T, the midpoint defines a partition of edges into two sets, inducing a vertex separation whose order is the number of vertices incident to edges in both sets; the width of the decomposition is the maximum such order over all midpoints, and the branchwidth is the minimum width over all branch-decompositions. This parameter captures the "treelike" nature of edge connectivity, with branchwidth at most $k$k implying efficient decompositions for minor-closed properties. Branchwidth and treewidth are closely related, satisfying $\mathrm{bw}(G) \leq \mathrm{tw}(G) + 1 \leq \frac{3}{2} \mathrm{bw}(G)$bw(G)≤tw(G)+1≤23​bw(G), allowing algorithms to interchange the measures with a constant factor loss in planar settings.^[98] Carving-width extends branchwidth concepts to vertex-based hierarchical separations, particularly suited for analyzing routing or clustering in graphs. Defined via a carving-decomposition—an unrooted binary tree with leaves bijectively labeled by vertices of $G$G—the width of an edge in the tree is the number of edges in $G$G crossing the bipartition of vertices induced by the subtrees, and the carving-width is the minimum maximum width over all such decompositions. This measure, equivalent to the minimum congestion in a call-routing tree for complete pairwise connections, is NP-hard to compute but polynomial-time solvable for planar graphs using dynamic programming along optimal branch-decompositions of derived structures. Like branchwidth, carving-width bounds the complexity of search problems, with graphs of carving-width at most 3 characterized as those with maximum degree at most 3 and treewidth at most 2.^[100]

Algebraic and Spectral Aspects

Matrices and Representations

In graph theory, matrices provide algebraic representations of graphs that encode structural information such as adjacency, incidence, and degrees, facilitating computations in areas like spectral analysis and optimization.^[101] These representations are particularly useful for finite, labeled graphs, where vertices correspond to rows and columns.^[102] Common matrices include the adjacency matrix, incidence matrix, and Laplacian matrix, each capturing different aspects of the graph's connectivity. The adjacency matrix $A$A of a simple undirected graph $G = (V, E)$G=(V,E) with vertex set $V = \{v_1, \dots, v_n\}$V={v1​,…,vn​} is an $n \times n$n×n symmetric matrix where the entry $A_{ij} = 1$Aij​=1 if there is an edge between $v_i$vi​ and $v_j$vj​, and $A_{ij} = 0$Aij​=0 otherwise; the diagonal entries are zero since simple graphs have no loops.^[101] For weighted graphs, the entries $A_{ij}$Aij​ are replaced by the weight of the edge between $v_i$vi​ and $v_j$vj​, or zero if no edge exists.^[103] In multigraphs, $A_{ij}$Aij​ equals the number of edges connecting $v_i$vi​ and $v_j$vj​. The incidence matrix $B$B of a graph $G$G with $n$n vertices and $m$m edges has rows indexed by vertices and columns by edges, where for an undirected graph, $B_{ie} = 1$Bie​=1 if vertex $v_i$vi​ is incident to edge $e$e, and 0 otherwise.^[104] For directed graphs, the matrix is oriented such that $B_{ie} = 1$Bie​=1 if $e$e originates at $v_i$vi​, $B_{ie} = -1$Bie​=−1 if $e$e terminates at $v_i$vi​, and 0 otherwise.^[105] The degree matrix $D$D is an $n \times n$n×n diagonal matrix with $D_{ii}$Dii​ equal to the degree of vertex $v_i$vi​.^[106] The Laplacian matrix $L$L is then defined as $L = D - A$L=D−A, where $A$A is the adjacency matrix; its entries satisfy $L_{ii} = \deg(v_i)$Lii​=deg(vi​) and $L_{ij} = -1$Lij​=−1 if $v_i$vi​ and $v_j$vj​ are adjacent (or the negative weight for weighted graphs), and 0 otherwise.^[106][107] Another representation is the deck of a graph $G$G, which is the multiset of all induced subgraphs obtained by deleting one vertex from $G$G (known as cards); which, according to the open reconstruction conjecture, determines the structure of $G$G up to isomorphism for graphs with at least three vertices.^[108] For example, the spectrum of a graph, consisting of the eigenvalues of its adjacency matrix, provides a multiset invariant that distinguishes many non-isomorphic graphs.^[109]

Spectrum, Eigenvalues, and Invariants

The spectrum of a graph refers to the multiset of eigenvalues of its adjacency matrix or Laplacian matrix, which encode algebraic invariants that reveal structural properties such as connectivity and expansion. For the adjacency matrix $A$A of an undirected graph, the eigenvalues are real and can be ordered as $\theta_1 \geq \theta_2 \geq \cdots \geq \theta_n$θ1​≥θ2​≥⋯≥θn​, where the spectral radius $\rho(G) = \theta_1$ρ(G)=θ1​ is the largest eigenvalue, satisfying $\rho(G) \geq 2|E|/|V|$ρ(G)≥2∣E∣/∣V∣ (the average degree) for a connected graph $G$G with $|V|$∣V∣ vertices and $|E|$∣E∣ edges, thus providing an upper bound on the average degree.^[110] The Laplacian matrix $L = D - A$L=D−A, where $D$D is the degree matrix, has eigenvalues $0 = \mu_1 \leq \mu_2 \leq \cdots \leq \mu_n$0=μ1​≤μ2​≤⋯≤μn​ that are nonnegative, with the multiplicity of 0 equal to the number of connected components.^[110] In regular graphs of degree $k$k, the largest adjacency eigenvalue equals the degree, $\theta_1 = k$θ1​=k, by the Perron-Frobenius theorem applied to the nonnegative irreducible adjacency matrix, and all other eigenvalues satisfy $|\theta_i| \leq k$∣θi​∣≤k.^[111] The spectral radius plays a key role in expander graphs, where the Alon-Boppana bound states that for any family of $d$d-regular graphs with girth tending to infinity, the second-largest eigenvalue magnitude approaches at least $2\sqrt{d-1}$2d−1

​, limiting expansion. Ramanujan graphs achieve the optimal bound, with all nontrivial eigenvalues bounded by $2\sqrt{d-1}$2d−1

​ in absolute value, as constructed explicitly using Cayley graphs of $\mathrm{SL}_2(\mathbb{Z}/p\mathbb{Z})$SL2​(Z/pZ) for prime powers $p \equiv 1 \pmod{d}$p≡1(modd).^[112] The algebraic connectivity, defined as the second-smallest Laplacian eigenvalue $\mu_2 > 0$μ2​>0 for connected graphs, quantifies how well-connected the graph is; smaller values indicate near-bipartiteness or bottlenecks, while larger values suggest robustness. Introduced by Fiedler, it bounds the vertex connectivity and relates to the graph's diameter.^[113][110] The spectral gap, often $\mu_2$μ2​ or $d - \theta_2$d−θ2​ for regular graphs, connects to combinatorial expansion via Cheeger's inequality: for a $d$d-regular graph, the Cheeger constant $h(G)$h(G) (minimum edge expansion over cuts) satisfies $h(G)^2 / 2 \leq d - \theta_2 \leq 2 h(G)$h(G)2/2≤d−θ2​≤2h(G), linking algebraic and isoperimetric properties.^[114] Another algebraic invariant is the Ihara zeta function, analogous to the Riemann zeta function, defined for a finite graph as $Z_G(u) = \prod_P (1 - u^{|P|})^{-1}$ZG​(u)=∏P​(1−u∣P∣)−1, where the product runs over primitive closed paths $P$P (backtrackless, non-backtracking walks). It equals the reciprocal of a polynomial whose roots relate to the adjacency eigenvalues, providing insights into cycle structures and coverings, as formalized by Bass for trees and extended to general graphs.

Extremal and Random Graphs

Turán Graphs and Extremal Properties

In extremal graph theory, the Turán graph $T(n,r)$T(n,r) is defined as the complete $r$r-partite graph on $n$n vertices with partite sets differing in size by at most one, maximizing the number of edges among all graphs on $n$n vertices that do not contain a complete subgraph $K_{r+1}$Kr+1​.^[115] This construction ensures that no clique of size $r+1$r+1 can form, as all vertices within a partite set are independent, while edges connect every pair of vertices from different sets.^[115] The extremal function $\mathrm{ex}(n, H)$ex(n,H) denotes the maximum number of edges in an $n$n-vertex graph that avoids a fixed forbidden subgraph $H$H.^[116] Turán's theorem establishes that for $H = K_{r+1}$H=Kr+1​, this maximum is precisely the number of edges in $T(n,r)$T(n,r), providing the sharp bound $\mathrm{ex}(n, K_{r+1}) = \left(1 - \frac{1}{r}\right) \frac{n^2}{2}$ex(n,Kr+1​)=(1−r1​)2n2​ asymptotically.^[117] Proved by Paul Turán in 1941, this result generalizes earlier work and forms the cornerstone of extremal graph theory by determining the densest $K_{r+1}$Kr+1​-free graphs. A prominent special case is Mantel's theorem, which corresponds to $r=2$r=2 and states that the maximum number of edges in a triangle-free graph on $n$n vertices is $\left\lfloor \frac{n^2}{4} \right\rfloor$⌊4n2​⌋, achieved by the complete bipartite graph $T(n,2) = K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$T(n,2)=K⌊n/2⌋,⌈n/2⌉​.^[117] Originally proved by Willem Mantel in 1907, this identifies the balanced complete bipartite graph as the unique extremal example for avoiding $K_3$K3​.^[118] For bipartite forbidden subgraphs, the Zarankiewicz problem extends these ideas by seeking the maximum number of edges in a bipartite graph on $m \times n$m×n vertices without a complete bipartite subgraph $K_{s,t}$Ks,t​, denoted $z(m,n;s,t)$z(m,n;s,t).^[119] Posed by Kazimierz Zarankiewicz in 1951, this remains largely open but provides bounds analogous to Turán's for bipartite extremal settings, with constructions like projective planes yielding lower bounds in specific cases.

Random Graphs and Expansion

In the Erdős–Rényi model, denoted G(n, p), a random graph on n vertices is generated by including each possible edge independently with probability p, providing a foundational probabilistic framework for studying graph properties in an average-case setting.^[120] This model captures the emergence of structural features as p varies relative to n, distinguishing it from deterministic constructions by emphasizing typical behavior over worst-case scenarios. Seminal work established that for p = c/n with c > 1 fixed, the graph contains a unique giant component comprising a positive fraction Θ(n) of vertices, while for c < 1, all components remain sublinear in size.^[121] A sharper threshold governs global connectivity: the graph G(n, p) becomes connected with high probability (approaching 1 as n → ∞) when p exceeds (log n)/n, marking the point where isolated vertices and small components vanish.^[122] This transition highlights the model's phase-like behavior, where connectivity arises abruptly around this density. Expander graphs generalize strong mixing properties observed in random graphs, defined as d-regular graphs where every subset S of vertices with |S| ≤ n/2 expands to at least α|S| neighbors for some expansion factor α > 1, ensuring efficient connectivity and mixing.^[123] The strong Cheeger constant quantifies this via h(G) = min_{S ⊆ V, 0 < |S| ≤ n/2} |E(S, V \ S)| / |S|, measuring the minimal edge boundary relative to set size; high values indicate robust expansion, as random d-regular graphs achieve h(G) ≈ d/2 with high probability.^[124] Optimal expanders, known as Ramanujan graphs, attain the Alon-Boppana bound on expansion, constructed explicitly using Cayley graphs of SL(2, q) for prime powers q, yielding families with second-largest eigenvalue bounded by 2√(d-1) in absolute value, achieving the optimal spectral gap of d - 2√(d-1). Quasi-random graphs extend this by characterizing deterministic sequences {G_n} that mimic G(n, 1/2) in edge distribution, such as uniform edge counts across induced subgraphs or balanced bipartite cuts, formalized through properties like the discrepancy in triangle densities being o(n^3).^[125] These sequences behave probabilistically without randomness, enabling pseudorandom constructions in algorithms and number theory. Small-world networks, as modeled by rewiring a fraction of edges in a lattice, exemplify random graph traits with high local clustering (like regular graphs) alongside short average path lengths O(log n) (like Erdős–Rényi), capturing real-world phenomena such as social connections where distant individuals are linked through few intermediaries.^[126]

Symbols and Notation

Greek Letters and Symbols

In graph theory, Greek letters are commonly employed to denote key parameters and invariants of graphs, providing a concise notation for structural properties. These symbols facilitate the discussion of concepts such as independence, coloring, degrees, connectivity, and spectral characteristics, often rooted in foundational works and standard references. The following catalogs prominent Greek symbols used in this context, focusing on their definitions and significance. The symbol $\alpha(G)$α(G) represents the independence number of a graph $G$G, which is the cardinality of the largest independent set in $G$G—a set of vertices with no two adjacent.^[66] This parameter measures the maximum subset of vertices that can be selected without forming an edge, and it is central to problems in optimization and coding theory.^[66] The symbol $\beta(G)$β(G) denotes the vertex cover number of $G$G, the size of the smallest vertex cover—a set of vertices that includes at least one endpoint of every edge in $G$G.^[127] Notably, $\beta(G)$β(G) is the complement of the independence number, satisfying $\beta(G) = |V(G)| - \alpha(G)$β(G)=∣V(G)∣−α(G), reflecting the duality between uncovered vertices and independent sets.^[127] The chromatic number is denoted by $\chi(G)$χ(G), the smallest number of colors required to color the vertices of $G$G such that no two adjacent vertices share the same color.^[67] This invariant quantifies the minimum partitioning of vertices into independent sets and is fundamental to scheduling and register allocation problems. The edge chromatic number, or chromatic index, is $\chi'(G)$χ′(G), the minimum colors needed for edges so that no two adjacent edges share a color. By Vizing's theorem, for any simple graph $G$G, $\chi'(G) = \Delta(G)$χ′(G)=Δ(G) or $\chi'(G) = \Delta(G) + 1$χ′(G)=Δ(G)+1. The minimum degree of $G$G is $\delta(G)$δ(G), the smallest degree among all vertices in $G$G, while the maximum degree is $\Delta(G)$Δ(G), the largest degree.^[128] These measures bound the graph's density and connectivity; for instance, Dirac's theorem on Hamiltonian cycles requires $\delta(G) \geq |V(G)|/2$δ(G)≥∣V(G)∣/2. Vertex connectivity is $\kappa(G)$κ(G), the minimum number of vertices whose removal disconnects $G$G (or reduces it to a single vertex).^[40] Edge connectivity is $\lambda(G)$λ(G), the minimum edges whose removal disconnects $G$G. A key relation is $\kappa(G) \leq \lambda(G) \leq \delta(G)$κ(G)≤λ(G)≤δ(G), ensuring robustness assessments.^[129][40] The symbol $c(G)$c(G) denotes the circumference of $G$G, the length (number of edges) of the longest cycle in $G$G.^[130] This parameter captures the graph's cyclic extent, with applications in Hamiltonian path detection; for example, in trees, $c(G) = 0$c(G)=0 due to acyclicity.^[130] Finally, $\rho(G)$ρ(G) is the spectral radius of $G$G, the largest absolute value of the eigenvalues of its adjacency matrix. This value, often the Perron-Frobenius eigenvalue for connected graphs, relates to the graph's growth rate and is pivotal in spectral graph theory for bounding expansion properties.^[131]

Roman Letters and Abbreviations

In graph theory, Roman letters and abbreviations denote fundamental structures, operations, and complexity classifications, providing a standardized notation for describing graphs, their variants, and associated algorithms. These symbols facilitate concise communication of concepts ranging from basic graph forms to search methods and computational hardness. The following entries cover key examples, emphasizing their structural properties and usage. G: A generic graph $G$G is typically represented as an ordered pair $(V, E)$(V,E), where $V$V is a finite set of vertices and $E$E is a set of unordered pairs from $V$V (for undirected graphs) or ordered pairs (for directed graphs), capturing the essential components without specifying further properties.^[132] K_n: The complete graph $K_n$Kn​ on $n$n vertices is an undirected simple graph where every pair of distinct vertices is connected by a unique edge, resulting in $\binom{n}{2} = \frac{n(n-1)}{2}$(2n​)=2n(n−1)​ edges and making it the densest possible graph on $n$n vertices.^[57] P_n and C_n: The path graph $P_n$Pn​ consists of $n$n vertices connected in a linear sequence by $n-1$n−1 edges, forming a tree with exactly two vertices of degree 1 (the endpoints) and the rest of degree 2; it serves as a basic connected acyclic structure.^[133] The cycle graph $C_n$Cn​ (for $n \geq 3$n≥3) is formed by connecting the endpoints of $P_n$Pn​ with an additional edge, creating a 2-regular connected graph with $n$n edges and no other cycles, often used to study circular connectivity.^[134] T(n,r): The Turán graph $T(n,r)$T(n,r) is the complete $r$r-partite graph on $n$n vertices with parts as equal in size as possible, maximizing the number of edges without containing a complete subgraph $K_{r+1}$Kr+1​; it achieves $\left(1 - \frac{1}{r}\right) \frac{n^2}{2}$(1−r1​)2n2​ edges asymptotically and exemplifies extremal graph constructions.^[135] DAG: A directed acyclic graph (DAG) is a directed graph with no directed cycles, allowing a topological ordering of vertices where edges only point from earlier to later vertices in the order; it models dependencies in scheduling and computation.^[136] H-free graphs: An $H$H-free graph is one that contains no subgraph isomorphic to a fixed graph $H$H, central to extremal graph theory for bounding edge counts or other properties in graphs avoiding specific forbidden substructures.^[137] BFS and DFS: Breadth-first search (BFS) is a graph traversal algorithm that explores vertices level by level from a starting source, using a queue to visit neighbors before deeper nodes, yielding shortest paths in unweighted graphs.^[138] Depth-first search (DFS) traverses as far as possible along each branch before backtracking, using a stack or recursion to explore deep paths first, useful for detecting cycles and connected components.^[138] NP: In the context of graph problems, NP (nondeterministic polynomial time) denotes the complexity class of decision problems verifiable in polynomial time, with many graph theory challenges like Hamiltonian cycle or graph coloring being NP-complete, implying no known efficient algorithms unless P=NP.^[139]

References

1. https://math.gordon.edu/courses/mat230/handouts/graphs.pdf
2. https://jlmartin.ku.edu/courses/math410-S13/graphs.pdf
3. https://math.arizona.edu/~kglasner/math443/BondyMurtyGTWA.pdf
4. https://sites.math.rutgers.edu/~zeilberg/akherim/wilsongraph.pdf
5. https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/f471f7b7034fabe8bbba5507df7d307f_MIT6_042JF10_chap05.pdf
6. https://web.math.princeton.edu/math_alive/5/Lab1/Defs.html
7. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory/lecture6.pdf
8. https://www.cs.columbia.edu/~gross/research/DigraphEmb-CGH-EuroJC.pdf
9. https://www.academia.edu/101212464/Some_Basic_Definitions_in_Graph_Theory
10. https://www.ub.edu/comb/koljaknauer/Adi_Avabis.pdf
11. https://math.unm.edu/~loring/links/graph_s07/incidenceDef.pdf
12. https://faculty.etsu.edu/gardnerr/5340/notes-Bondy-Murty-GT/Bondy-Murty-GT-1-1.pdf
13. https://ocw.mit.edu/courses/16-01-unified-engineering-i-ii-iii-iv-fall-2005-spring-2006/a86346b619ae7fc482e7919bc7a03169_graphshandout.pdf
14. https://www3.nd.edu/~dgalvin1/60610/60610_S09/60610graphnotation.pdf
15. https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/e6db7638031b754f5f68012946af4763_MIT6_042JF10_chap06.pdf
16. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory/lecture19.pdf
17. https://www.math.fsu.edu/~pkirby/mad2104/SlideShow/s6_1.pdf
18. https://people.cs.uchicago.edu/~laci/reu04/n05.hdir/node2.html
19. https://scholar.rose-hulman.edu/cgi/viewcontent.cgi?article=1004&context=math_mstr
20. https://sites.pitt.edu/~bonidie/graph.html
21. https://www3.nd.edu/~dgalvin1/40210/40210_F12/CGT_early.pdf
22. https://mathworld.wolfram.com/VertexDegree.html
23. https://www.cs.cornell.edu/courses/cs2802/2020sp/2802graphtheory.pdf
24. https://mathworld.wolfram.com/RegularGraph.html
25. https://mathworld.wolfram.com/GraphNeighborhood.html
26. https://www.cs.cmu.edu/afs/cs/academic/class/15210-f14/www/lectures/graph-intro.pdf
27. https://people.computing.clemson.edu/~goddard/papers/distanceChapter.pdf
28. https://mathworld.wolfram.com/GraphEccentricity.html
29. https://mathworld.wolfram.com/GraphDiameter.html
30. https://www.sciencedirect.com/science/article/pii/0095895689900294
31. https://www.combinatorics.org/files/Surveys/ds14/ds14v2-2013.pdf
32. https://mathworld.wolfram.com/MooreGraph.html
33. https://mathworld.wolfram.com/ConnectedComponent.html
34. https://mathworld.wolfram.com/WeaklyConnectedComponent.html
35. https://mathworld.wolfram.com/StronglyConnectedComponent.html
36. https://mathworld.wolfram.com/ArticulationVertex.html
37. https://cp-algorithms.com/graph/bridge-searching.html
38. https://mathworld.wolfram.com/Block.html
39. https://mathworld.wolfram.com/VertexCut.html
40. https://mathworld.wolfram.com/VertexConnectivity.html
41. https://cp-algorithms.com/graph/edge_vertex_connectivity.html
42. https://mathworld.wolfram.com/EdgeContraction.html
43. https://www.cs.rpi.edu/~slotag/classes/SU19/slides/lec10.pdf
44. https://mathworld.wolfram.com/CactusGraph.html
45. https://mathworld.wolfram.com/GraphRadius.html
46. https://mathworld.wolfram.com/GraphPeriphery.html
47. https://mathweb.ucsd.edu/~gmckinley/154_sp22/154-notes-2021.pdf
48. https://www.researchgate.net/publication/226041435_Some_properties_of_graph_centroids
49. https://www.cs.huji.ac.il/~nati/PAPERS/ge_ge_gr.pdf
50. https://www.cs.rpi.edu/~slotag/classes/SP20t/slides/lec06.pdf
51. https://people.cs.umass.edu/~barring/cs250s12/lecture/22.pdf
52. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory/lecture10.pdf
53. https://www.cs.cmu.edu/~odonnell/papers/caterpillar-covariance.pdf
54. https://mathworld.wolfram.com/BipartiteGraph.html
55. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory/lecture4.pdf
56. https://mathworld.wolfram.com/CompleteBipartiteGraph.html
57. https://mathworld.wolfram.com/CompleteGraph.html
58. https://mathworld.wolfram.com/Clique.html
59. https://arxiv.org/abs/2404.04680
60. https://arxiv.org/abs/2009.00130
61. https://mathworld.wolfram.com/CrownGraph.html
62. https://arxiv.org/abs/1609.00674
63. https://mathworld.wolfram.com/MaximalClique.html
64. https://mathworld.wolfram.com/CliqueNumber.html
65. https://faculty.fiu.edu/~ramsamuj/graphtheory/chap8.pdf
66. https://mathworld.wolfram.com/IndependenceNumber.html
67. https://mathworld.wolfram.com/ChromaticNumber.html
68. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory/lecture25.pdf
69. https://aimath.org/WWN/perfectgraph/perfectgraph.pdf
70. https://thomas.math.gatech.edu/SLIDE/perfsl.pdf
71. https://mathworld.wolfram.com/Claw-FreeGraph.html
72. https://www.web.math.princeton.edu/~mchudnov/claws_survey.pdf
73. https://mathworld.wolfram.com/GroetzschGraph.html
74. https://www.pnas.org/doi/pdf/10.1073/pnas.43.9.842
75. https://math.nist.gov/~JBernal/p_t_f.pdf
76. https://web.eecs.umich.edu/~pettie/matching/Tutte-the-factors-of-graphs.pdf
77. http://web.eecs.umich.edu/~pettie/matching/Gallai-max-min-thms-for-graphs-in-German.pdf
78. https://link.springer.com/article/10.1007/BF01456961
79. https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf
80. https://www.cs.yale.edu/homes/spielman/561/2009/lect25-09.pdf
81. https://discrete.openmathbooks.org/dmoi3/sec_planar.html
82. https://ti.inf.ethz.ch/ew/courses/Geo19/lecture/gca19-2.pdf
83. https://cs.brown.edu/people/rtamassi/gdhandbook/chapters/straightline.pdf
84. https://www.ics.uci.edu/~eppstein/junkyard/euler/
85. https://eudml.org/doc/212352
86. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory/lecture21.pdf
87. https://reu.dimacs.rutgers.edu/~michaels/Presentation2.pdf
88. https://web.math.princeton.edu/~nalon/PDFS/gembed8.pdf
89. https://www.infosun.fim.uni-passau.de/~chris/down/Outer1Planar.pdf
90. https://ir.library.louisville.edu/etd/33/
91. https://repub.eur.nl/pub/23560/EI2011-16.pdf
92. https://dwest.web.illinois.edu/pubs/outerpl.pdf
93. https://courses.grainger.illinois.edu/cs498mv/fa2018/SeriesParallel.pdf
94. https://www.ecei.tohoku.ac.jp/alg/nishizeki/sub/j/DVD/PDF_J/J037.pdf
95. https://www.graphclasses.org/classes/gc_275.html
96. https://www.sciencedirect.com/science/article/pii/S0012365X05006102
97. https://epubs.siam.org/doi/10.1137/0213035
98. https://web.math.princeton.edu/~pds/papers/GM10/paper.pdf
99. https://www.cs.tau.ac.il/~haimk/papers/pw.ps
100. https://thomas.math.gatech.edu/PAP/ratcatch.pdf
101. https://mathworld.wolfram.com/AdjacencyMatrix.html
102. https://link.springer.com/chapter/10.1007/978-1-84882-981-7_3
103. https://link.springer.com/article/10.1007/s10114-024-3127-9
104. https://mathworld.wolfram.com/IncidenceMatrix.html
105. https://link.springer.com/chapter/10.1007/978-1-84882-981-7_2
106. https://mathworld.wolfram.com/LaplacianMatrix.html
107. https://link.springer.com/chapter/10.1007/978-1-84882-981-7_4
108. https://faculty.etsu.edu/gardnerr/5340/notes-Bondy-Murty-GT/Bondy-Murty-GT-2-7.pdf
109. https://mathworld.wolfram.com/GraphSpectrum.html
110. https://homepages.cwi.nl/~aeb/math/ipm/ipm.pdf
111. https://www.cambridge.org/core/books/algebraic-graph-theory/6C70471342F19680068C35EF174075DC
112. https://fanchung.ucsd.edu/wp/eigenlb.pdf
113. https://dml.cz/bitstream/handle/10338.dmlcz/101168/CzechMathJ_23-1973-2_11.pdf
114. https://www.sciencedirect.com/science/article/pii/0095895685900929
115. https://mathworld.wolfram.com/TuranGraph.html
116. https://mathworld.wolfram.com/ExtremalGraph.html
117. https://mathworld.wolfram.com/TuransTheorem.html
118. https://www.advancesincombinatorics.com/article/12043-a-rainbow-version-of-mantel-s-theorem
119. https://arxiv.org/abs/2410.03702
120. https://snap.stanford.edu/class/cs224w-readings/erdos59random.pdf
121. https://snap.stanford.edu/class/cs224w-readings/erdos60random.pdf
122. https://users.renyi.hu/~p_erdos/1961-19.pdf
123. https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf
124. https://people.seas.harvard.edu/~salil/pseudorandomness/expanders.pdf
125. https://www.math.ucsd.edu/~ronspubs/88_04_quasi_graphs.pdf
126. http://snap.stanford.edu/class/cs224w-readings/watts98smallworld.pdf
127. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory-slides-3.pdf
128. https://mathworld.wolfram.com/MaximumVertexDegree.html
129. https://mathworld.wolfram.com/EdgeConnectivity.html
130. https://mathworld.wolfram.com/GraphCircumference.html
131. https://mathworld.wolfram.com/SpectralRadius.html
132. https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_and_Graph_Theory_%28Guichard%29/05%253A_Graph_Theory/5.01%253A_The_Basics_of_Graph_Theory
133. https://mathworld.wolfram.com/PathGraph.html
134. https://webhomes.maths.ed.ac.uk/~v1ranick/papers/wilsongraph.pdf
135. https://www.comm.utoronto.ca/~frank/notes/turan.pdf
136. https://people.ciirc.cvut.cz/~hlavac/TeachPresEn/05Mathematics/08GraphTheoryAndAlgorithms.pdf
137. https://people.maths.ox.ac.uk/keevash/papers/hfree-process-journal.pdf
138. https://cs.stanford.edu/people/abisee/gs.pdf
139. https://people.eecs.berkeley.edu/~vazirani/algorithms/chap8.pdf