# connected graph

## Primary tabs

Defines:
strongly connected graph, connected components, strongly connected components
Synonym:
connected, strongly connected, component
Type of Math Object:
Definition
Major Section:
Reference
Groups audience:

## Mathematics Subject Classification

### 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/