About MATtours
Site mapGallery of graphs and algorithmsHow to teach using investigationsClickable list of termsHelp

Connection and components

Two vertices are said to be connected when a path between them exists. A graph is said to be connected when every two of its vertices are connected. A graph that is not connected is disconnected.

A connected component ( or simply component) of a graph is the maximal subgraph whose vertices are all connected. A connected graph has a single component, and that is the graph itself. A disconnected graph will have at least two components. A block is a special kind of connected graph or subgraph.

disconnected This graph is connected.
connected This graph is not connected.

Sometimes there is no way of looking at a drawing such as the disconnected one without any other context and know if it is a single graph that is not connected or two graphs that are drawn near one another. The context must make it clear that it is one graph.

Connectivity is the term used to refer to the number of edges or vertices you must delete form a graph in order to disconnect it.

Copyright © 1999-2000 SciMathMN