# Connectivity (graph theory)

### The Television & Movie Wiki: for TV, celebrities, and movies.

In mathematics and computer science the **connectivity** of graphs is one of the basic concepts of graph theory. It is closely related to the concept of path.

In network theory we are often interested how many connections (edges) in the network are allowed to fail before two nodes (vertices) become disconnected. Menger's theorem and Fulkerson's theorem provide characterizations of this problem.

By adding weights to the edges of the graph we are able to consider network flow problems which allow a finer discussion of connectivity.

Checking if a graph is connected, or even its number of connected components, is a very easy problem that can be solved in deterministic logarithmic space (see SL).

## Contents |

## Connections

Given an undirected graph, two vertices *u* and *v* are called **connected** if there exists a path from *u* to *v*. Otherwise they are called **disconnected**. The graph is called **connected graph** if every pair of vertices in the graph is connected.

## Cuts

A **vertex cut** for two vertices *u* and *v* is a set of vertices whose removal from the graph disconnects *u* and *v*. A vertex cut for the whole graph is a set of vertices whose removal renders the graph disconnected. The **vertex connectivity** κ(*G*) for a graph *G* is the size of minimum vertex cut. A graph is called **k-vertex-connected** if its vertex connectivity is *k* or greater.

The same concept can be defined for edges.

An **edge cut** for two vertices *u* and *v* is a set of edges whose removal from the graph disconnects *u* and *v*. A edge cut for the whole graph is a set of edges whose removal renders the graph disconnected. The **edge connectivity** κ'(*G*) for a graph *G* is the size of the minimum edge cut. A graph is called **k-edge-connected** if its edge connectivity is *k* or greater.

## Examples

- The vertex and edge connectivities of a disconnected graph are both 0
- A connected graph is 1-connected by definition
- A complete graph is
*maximally connected*; if it has*n*vertices, its edge connectivity is*n* - A tree is
*minimally connected*; its edge connectivity is 1

## Properties

- Connectedness is preserved by graph homomorphisms.
- If
*G*is connected then the line graph*L*(*G*) is connected too. - A graph is
*k*-vertex-connected if and only if it contains*k*vertex independent paths between any two vertices. - A graph is
*k*-edge-connected if and only if it contains*k*edge independent paths between any two edges. - Given a
*k*-vertex-connected graph*G*then for every set of vertices*U*there exists a cycle in*G*containing*U* - Given a connected graph the distance between two vertices
*u*and*v*is equal to the number of pairwise disjunct edge cut sets which separate*u*and*v*.