# Definition: Connected and Disconnected Graphs, Bridges and Cutvertices

Let $$G(V,E,\gamma)$$ be a non-empty undirected graph. * $$G$$ is called connected, if there is a path $$P=w-u$$ between any two of its vertices $$w$$ and $$u$$. Equivalently, a connected graph has exactly one component, i.e. the output of the algorithm get_components(G) is a set $$C$$ of subgraphs with $$|C|=1$$. * $$G$$ is called disconnected, if it has more than one component, i.e. if it is not connected. * An edge in a connected graph is a bridge, if its removal leaves a disconnected graph. * A vertex of a connected graph is a cutvertex or articulation point, if its removal leaves a disconnected graph.

#### Examples:

The above graph $$G$$, consisting of $$14$$ vertices is disconnected. However, It has the following conntected components:

• $$G[1,2,3,4,5,6,7,8]$$
• $$G[9,10]$$
• $$G[11,12,13]$$
• $$G[ 14 ]$$

The edge $$(3,6)$$ is a bridge of the component $$G[1,2,3,4,5,6,7,8]$$ and the edge $$(9,11)$$ is a bridge of the component $$G[9,10]$$.

The vertices $$3$$ and $$4$$ are articulation points of the component $$G[1,2,3,4,5,6,7,8]$$.

Algorithms: 1
Corollaries: 2
Definitions: 3 4
Proofs: 5 6 7 8 9 10 11 12 13 14
Propositions: 15 16
Theorems: 17 18 19 20 21 22 23 24 25 26

Thank you to the contributors under CC BY-SA 4.0!

Github:

### References

#### Bibliography

1. Aldous Joan M., Wilson Robin J.: "Graphs and Applications - An Introductory Approach", Springer, 2000
2. Diestel, Reinhard: "Graph Theory, 3rd Edition", Springer, 2005