Connectivity

Definition of Connectivity

A $connected$ graph is one in which for every pair of its $vertices$ there exists a $path$ connecting them.

If no such $path$ exists for some pair, the graph is $disconnected$ .

A $connected component$ of a graph is a maximal $connected$ $subgraph$ — you cannot add any other vertex or edge from the original graph without breaking connectivity.

connected components.png
Figure 0. Connected components of a graph.

The vertex sets of all $connected components$ form a partition of $V (G)$ , meaning each vertex belongs to exactly one component.

connected unconnected.png|500
Figure 1. Connected and disconnected graphs.

$Example$
Consider a social network graph split into two groups with no friendships between them; each group is a $connected component$ and the entire graph is $disconnected$ .

$Metaphor$
A $connected component$ is like an isolated island of people who all know each other, with no bridges to other islands.

Forests and Trees

A $forest$ is an $acyclic$ graph — there are no $cycles$ in any of its $subgraphs$ .

Each $connected component$ of a $forest$ is called a $tree$ .

A fundamental property is that any $tree$ of order $n$ (having $n$ $vertices$ ) has exactly $n - 1$ $edges$ .

Important Property of Trees

$E (T) = V (T) - 1$

where $E (T)$ is the number of edges and $V (T)$ is the number of vertices in a tree $T$ .
This property holds for all trees, regardless of their structure or size.

This $tree$ property underlies many algorithms, such as constructing minimum spanning trees and organizing hierarchical data.

Tree Forest.png|500
Figure 2. Trees and forests.

$Example$
A corporate hierarchy chart with no circular reporting lines is a $forest$ , and each department’s chart is a $tree$ with one fewer reporting line than members.

$Metaphor$
A $forest$ is like a grove of family trees, each $tree$ spreading branches without ever looping back.

Conclusion

We have defined $connected$ graphs and their maximal $connected components$ , noting that vertex sets of components partition the graph.

We then introduced $forests$ — graphs without $cycles$ — and explained that each component of a forest is a $tree$ with exactly one fewer edge than vertices.

These concepts of connectivity and acyclicity form the backbone of many graph-theoretic algorithms and real-world network models.