Definition:Component (Graph Theory)

Definition

Let $G$ be a graph.

Let $H$ be a subgraph of $G$ such that:

• $H$ is connected;

• $H$ is not contained in any connected subgraph of $G$ which has more vertices or edges than $H$ has.

Then $H$ is a component of $G$.

Example

This graph has 4 components:

Also see

• Connected graph: a graph with only one component.

Sources

• Gary Chartrand: Introductory Graph Theory (1977): $\S 2.3$