+- MKLab (https://mklab.gr)
+-- Forum: [INDEX] (https://mklab.gr/forumdisplay.php?fid=1)
+--- Forum: MATHEMATICS (https://mklab.gr/forumdisplay.php?fid=3)
+---- Forum: ARTICLES (https://mklab.gr/forumdisplay.php?fid=13)
+----- Forum: GRAPHS AND NETWORKS (https://mklab.gr/forumdisplay.php?fid=202)
+----- Thread: Component (/showthread.php?tid=1902)
Component - mklabgr - 09-07-2026
Component
A component, or connected component, of an undirected graph is a maximal connected subgraph: a collection of vertices in which every pair can be joined by a path, and which cannot be enlarged while remaining connected. Thus, the connected components partition the vertex set of a graph into disjoint subsets. A connected graph has exactly one component, while each isolated vertex forms its own component. Equivalently, define two vertices $u$ and $v$ to be related when there is a path from $u$ to $v$; this is an equivalence relation, and its equivalence classes are precisely the vertex sets of the connected components.
The number of components $c$ is an important invariant of a graph. For a graph with $n$ vertices, every spanning forest contains exactly $n-c$ edges. If the graph additionally has $m$ edges, its circuit rank is
m−n+c.m-n+c.
The number of components also appears in algebraic graph theory: it equals the multiplicity of the eigenvalue $0$ of the graph's Laplacian matrix. Components can be found efficiently using breadth-first search (BFS) or depth-first search (DFS) in linear time $O(n+m)$. When edges are progressively added, a disjoint-set (union–find) structure can maintain the components very efficiently. Connected-component algorithms also have practical applications in areas such as image analysis, where groups of adjoining pixels can be identified as separate objects.
Connected components become especially interesting in random graph theory. In the Erdős–Rényi model $G(n,p)$, the structure changes sharply as the edge probability $p$ increases. For $p<(1-\varepsilon)/n$, components are generally small; around the critical threshold $p\approx1/n$, components of order $n^{2/3}$ appear; and for $p>(1+\varepsilon)/n$, a single giant component containing a positive fraction of all vertices emerges. A still higher threshold around $p\sim(\log n)/n$ marks the transition from several components to a graph that is connected with high probability.
Key takeaways
- A connected component is a maximal connected part of a graph.
- Components partition all vertices into disjoint groups.
- They can be computed in $O(n+m)$ time using BFS or DFS.
- They connect graph theory with linear algebra, topology, algorithms, image processing, and random graphs.
ARTICLE