## You are here

Homeconnected graph

## Primary tabs

# connected graph

A *connected graph* is a graph such that there exists a path between all pairs of vertices. If the graph is a directed graph, and there exists a path from each vertex to every other vertex, then it is a *strongly connected graph*.

A *connected component* is a maximal (under inclusion) subset of vertices of any graph and any edges between them that forms a connected graph. Similarly, a *strongly connected component* is a maximal (under inclusion) subset of vertices of any digraph and any edges between them that forms a strongly connected graph. Any graph or digraph is a union of connected or strongly connected components, plus some edges to join the components together. Thus any graph can be decomposed into its connected or strongly connected components. For instance, Tarjan’s algorithm can decompose any digraph into its strongly connected components.

For example, the following graph and digraph are connected and strongly connected, respectively.

$\begin{array}[]{cc}\xymatrix{A\ar@{-}[r]\hfil&B\ar@{-}[r]&C\ar@{-}[d]\\ D\ar@{-}[r]&E\ar@{-}[r]&F&\xymatrix{A\ar[r]&B\ar[d]\ar[r]&C\ar[d]\\ D\ar[u]&E\ar[l]&F\ar[l]\end{array}$ |

On the other hand, the following graph is *not* connected, and consists of the union of two connected components.

$\xymatrix{A\ar@{-}[r]&B\ar@{-}[r]&C\\ D\ar@{-}[r]&E\ar@{-}[r]&F}$ |

The following digraph is *not* strongly connected, because there is
no way to reach $F$ from other vertices, and there is no vertex reachable from $C$.

$\xymatrix{A\ar[r]&B\ar[d]\ar[r]&C\\ D\ar[u]&E\ar[l]&F\ar[l]\ar[u]}$ |

The three strongly connected components of this graph are

$\begin{array}[]{ccc}\xymatrix{A\ar[r]\hfil&B\ar[d]\\ D\ar[u]&E\ar[l]&$C$&$F$\end{array}$ |

## Mathematics Subject Classification

05C40*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## connected component

In my correction (about not every subset that's connected being a connected *component*) i suggested added something along the lines of

> Let $X\sim Y$ denote there exists a path joining vertices X and Y;

> it is not hard to see $\sim$ is an equivalence relation. Each of

> its equivalence classes, together with the edges connected to the

> vertices in that class, is known as a (\emph{connected})

> \emph{component} of the graph.

>

> A \emph{connected graph} is one that consists of a single connected

> component.

I'm glad you didn't take this suggestion up (yet) because my use of the $\sim$ symbol is unfortunate. That notation is already in use for "are linked directly by an edge", not a transitive concept. For the (transitive) relation on vertices of being connected by a path, any other ad hoc symbol would do in the course of the argument, such as $\approx$.

--regards, marijke

http://web.mat.bham.ac.uk/marijke/