In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components.

The number of components in a given graph is an important graph invariant, and is closely related to invariants of matroids, topological spaces, and matrices. In random graphs, a frequently occurring phenomenon is the incidence of a giant component, one component that is significantly larger than the others; and of a percolation threshold, an edge probability above which a giant component exists and below which it does not.

The components of a graph can be constructed in linear time, and a special case of the problem, connected-component labeling, is a basic technique in image analysis. Dynamic connectivity algorithms maintain components as edges are inserted or deleted in a graph, in low time per change. In computational complexity theory, connected components have been used to study algorithms with limited space complexity, and sublinear time algorithms can accurately estimate the number of components.

A component of a given undirected graph may be defined as a connected subgraph that is not part of any larger connected subgraph. For instance, the graph shown in the first illustration has three components. Every vertex ${\displaystyle v}$ of a graph belongs to one of the graph's components, which may be found as the induced subgraph of the set of vertices reachable from ${\displaystyle v}$. Every graph is the disjoint union of its components. Additional examples include the following special cases:

Another definition of components involves the equivalence classes of an equivalence relation defined on the graph's vertices. In an undirected graph, a vertex ${\displaystyle v}$ is reachable from a vertex ${\displaystyle u}$ if there is a path from ${\displaystyle u}$ to ${\displaystyle v}$, or equivalently a walk (a path allowing repeated vertices and edges). Reachability is an equivalence relation, since:

The equivalence classes of this relation partition the vertices of the graph into disjoint sets, subsets of vertices that are all reachable from each other, with no additional reachable pairs outside of any of these subsets. Each vertex belongs to exactly one equivalence class. The components are then the induced subgraphs formed by each of these equivalence classes. Alternatively, some sources define components as the sets of vertices rather than as the subgraphs they induce.

Similar definitions involving equivalence classes have been used to defined components for other forms of graph connectivity, including the weak components and strongly connected components of directed graphs and the biconnected components of undirected graphs.

The number of components of a given finite graph can be used to count the number of edges in its spanning forests: In a graph with ${\displaystyle n}$ vertices and ${\displaystyle c}$ components, every spanning forest will have exactly ${\displaystyle n-c}$ edges. This number ${\displaystyle n-c}$ is the matroid-theoretic rank of the graph, and the rank of its graphic matroid. The rank of the dual cographic matroid equals the circuit rank of the graph, the minimum number of edges that must be removed from the graph to break all its cycles. In a graph with ${\displaystyle m}$ edges, ${\displaystyle n}$ vertices and ${\displaystyle c}$ components, the circuit rank is ${\displaystyle m-n+c}$.