# Connectivity (graph theory)

(Redirected from Connected graph)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into isolated subgraphs. Connectivity (graph theory)_sentence_0

It is closely related to the theory of network flow problems. Connectivity (graph theory)_sentence_1

The connectivity of a graph is an important measure of its resilience as a network. Connectivity (graph theory)_sentence_2

## Connected vertices and graphs Connectivity (graph theory)_section_0

In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v. Otherwise, they are called disconnected. Connectivity (graph theory)_sentence_3

If the two vertices are additionally connected by a path of length 1, i.e. by a single edge, the vertices are called adjacent. Connectivity (graph theory)_sentence_4

A graph is said to be connected if every pair of vertices in the graph is connected. Connectivity (graph theory)_sentence_5

This means that there is a path between every pair of vertices. Connectivity (graph theory)_sentence_6

An undirected graph that is not connected is called disconnected. Connectivity (graph theory)_sentence_7

An undirected graph G is therefore disconnected if there exist two vertices in G such that no path in G has these vertices as endpoints. Connectivity (graph theory)_sentence_8

A graph with just one vertex is connected. Connectivity (graph theory)_sentence_9

An edgeless graph with two or more vertices is disconnected. Connectivity (graph theory)_sentence_10

A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. Connectivity (graph theory)_sentence_11

It is unilaterally connected or unilateral (also called semiconnected) if it contains a directed path from u to v or a directed path from v to u for every pair of vertices u, v. It is strongly connected, or simply strong, if it contains a directed path from u to v and a directed path from v to u for every pair of vertices u, v. Connectivity (graph theory)_sentence_12

## Components and cuts Connectivity (graph theory)_section_1

A connected component is a maximal connected subgraph of an undirected graph. Connectivity (graph theory)_sentence_13

Each vertex belongs to exactly one connected component, as does each edge. Connectivity (graph theory)_sentence_14

A graph is connected if and only if it has exactly one connected component. Connectivity (graph theory)_sentence_15

The strong components are the maximal strongly connected subgraphs of a directed graph. Connectivity (graph theory)_sentence_16

A vertex cut or separating set of a connected graph G is a set of vertices whose removal renders G disconnected. Connectivity (graph theory)_sentence_17

The vertex connectivity κ(G) (where G is not a complete graph) is the size of a minimal vertex cut. Connectivity (graph theory)_sentence_18

A graph is called k-vertex-connected or k-connected if its vertex connectivity is k or greater. Connectivity (graph theory)_sentence_19

More precisely, any graph G (complete or not) is said to be k-vertex-connected if it contains at least k+1 vertices, but does not contain a set of k − 1 vertices whose removal disconnects the graph; and κ(G) is defined as the largest k such that G is k-connected. Connectivity (graph theory)_sentence_20

In particular, a complete graph with n vertices, denoted Kn, has no vertex cuts at all, but κ(Kn) = n − 1. Connectivity (graph theory)_sentence_21

A vertex cut for two vertices u and v is a set of vertices whose removal from the graph disconnects u and v. The local connectivity κ(u, v) is the size of a smallest vertex cut separating u and v. Local connectivity is symmetric for undirected graphs; that is, κ(u, v) = κ(v, u). Connectivity (graph theory)_sentence_22

Moreover, except for complete graphs, κ(G) equals the minimum of κ(u, v) over all nonadjacent pairs of vertices u, v. Connectivity (graph theory)_sentence_23

2-connectivity is also called biconnectivity and 3-connectivity is also called triconnectivity. Connectivity (graph theory)_sentence_24

A graph G which is connected but not 2-connected is sometimes called separable. Connectivity (graph theory)_sentence_25

Analogous concepts can be defined for edges. Connectivity (graph theory)_sentence_26

In the simple case in which cutting a single, specific edge would disconnect the graph, that edge is called a bridge. Connectivity (graph theory)_sentence_27

More generally, an edge cut of G is a set of edges whose removal renders the graph disconnected. Connectivity (graph theory)_sentence_28

The edge-connectivity λ(G) is the size of a smallest edge cut, and the local edge-connectivity λ(u, v) of two vertices u, v is the size of a smallest edge cut disconnecting u from v. Again, local edge-connectivity is symmetric. Connectivity (graph theory)_sentence_29

A graph is called k-edge-connected if its edge connectivity is k or greater. Connectivity (graph theory)_sentence_30

A graph is said to be maximally connected if its connectivity equals its minimum degree. Connectivity (graph theory)_sentence_31

A graph is said to be maximally edge-connected if its edge-connectivity equals its minimum degree. Connectivity (graph theory)_sentence_32

### Super- and hyper-connectivity Connectivity (graph theory)_section_2

A graph is said to be super-connected or super-κ if every minimum vertex cut isolates a vertex. Connectivity (graph theory)_sentence_33

A graph is said to be hyper-connected or hyper-κ if the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex. Connectivity (graph theory)_sentence_34

A graph is semi-hyper-connected or semi-hyper-κ if any minimum vertex cut separates the graph into exactly two components. Connectivity (graph theory)_sentence_35

More precisely: a G connected graph is said to be super-connected or super-κ if all minimum vertex-cuts consist of the vertices adjacent with one (minimum-degree) vertex. Connectivity (graph theory)_sentence_36

A G connected graph is said to be super-edge-connected or super-λ if all minimum edge-cuts consist of the edges incident on some (minimum-degree) vertex. Connectivity (graph theory)_sentence_37

A cutset X of G is called a non-trivial cutset if X does not contain the neighborhood N(u) of any vertex u ∉ X. Connectivity (graph theory)_sentence_38

Then the superconnectivity κ1 of G is: Connectivity (graph theory)_sentence_39

Connectivity (graph theory)_description_list_0

• κ1(G) = min{|X| : X is a non-trivial cutset}.Connectivity (graph theory)_item_0_0

A non-trivial edge-cut and the edge-superconnectivity λ1(G) are defined analogously. Connectivity (graph theory)_sentence_40

## Menger's theorem Connectivity (graph theory)_section_3

Main article: Menger's theorem Connectivity (graph theory)_sentence_41

One of the most important facts about connectivity in graphs is Menger's theorem, which characterizes the connectivity and edge-connectivity of a graph in terms of the number of independent paths between vertices. Connectivity (graph theory)_sentence_42

If u and v are vertices of a graph G, then a collection of paths between u and v is called independent if no two of them share a vertex (other than u and v themselves). Connectivity (graph theory)_sentence_43

Similarly, the collection is edge-independent if no two paths in it share an edge. Connectivity (graph theory)_sentence_44

The number of mutually independent paths between u and v is written as κ′(u, v), and the number of mutually edge-independent paths between u and v is written as λ′(u, v). Connectivity (graph theory)_sentence_45

Menger's theorem asserts that for distinct vertices u,v, λ(u, v) equals λ′(u, v), and if u is also not adjacent to v then κ(u, v) equals κ′(u, v). Connectivity (graph theory)_sentence_46

This fact is actually a special case of the max-flow min-cut theorem. Connectivity (graph theory)_sentence_47

## Computational aspects Connectivity (graph theory)_section_4

The problem of determining whether two vertices in a graph are connected can be solved efficiently using a search algorithm, such as breadth-first search. Connectivity (graph theory)_sentence_48

More generally, it is easy to determine computationally whether a graph is connected (for example, by using a disjoint-set data structure), or to count the number of connected components. Connectivity (graph theory)_sentence_49

A simple algorithm might be written in pseudo-code as follows: Connectivity (graph theory)_sentence_50

Connectivity (graph theory)_ordered_list_1

1. Begin at any arbitrary node of the graph, GConnectivity (graph theory)_item_1_1
2. Proceed from that node using either depth-first or breadth-first search, counting all nodes reached.Connectivity (graph theory)_item_1_2
3. Once the graph has been entirely traversed, if the number of nodes counted is equal to the number of nodes of G, the graph is connected; otherwise it is disconnected.Connectivity (graph theory)_item_1_3

By Menger's theorem, for any two vertices u and v in a connected graph G, the numbers κ(u, v) and λ(u, v) can be determined efficiently using the max-flow min-cut algorithm. Connectivity (graph theory)_sentence_51

The connectivity and edge-connectivity of G can then be computed as the minimum values of κ(u, v) and λ(u, v), respectively. Connectivity (graph theory)_sentence_52

In computational complexity theory, SL is the class of problems log-space reducible to the problem of determining whether two vertices in a graph are connected, which was proved to be equal to L by Omer Reingold in 2004. Connectivity (graph theory)_sentence_53

Hence, undirected graph connectivity may be solved in O(log n) space. Connectivity (graph theory)_sentence_54

The problem of computing the probability that a Bernoulli random graph is connected is called network reliability and the problem of computing whether two given vertices are connected the ST-reliability problem. Connectivity (graph theory)_sentence_55

Both of these are #P-hard. Connectivity (graph theory)_sentence_56

### Number of connected graphs Connectivity (graph theory)_section_5

The number of distinct connected labeled graphs with n nodes is tabulated in the On-Line Encyclopedia of Integer Sequences as sequence , through n = 16. Connectivity (graph theory)_sentence_57

The first few non-trivial terms are Connectivity (graph theory)_sentence_58

## Examples Connectivity (graph theory)_section_6

Connectivity (graph theory)_unordered_list_2

• The vertex- and edge-connectivities of a disconnected graph are both 0.Connectivity (graph theory)_item_2_4
• 1-connectedness is equivalent to connectedness for graphs of at least 2 vertices.Connectivity (graph theory)_item_2_5
• The complete graph on n vertices has edge-connectivity equal to n − 1. Every other simple graph on n vertices has strictly smaller edge-connectivity.Connectivity (graph theory)_item_2_6
• In a tree, the local edge-connectivity between every pair of vertices is 1.Connectivity (graph theory)_item_2_7

## Bounds on connectivity Connectivity (graph theory)_section_7

Connectivity (graph theory)_unordered_list_3

• The vertex-connectivity of a graph is less than or equal to its edge-connectivity. That is, κ(G) ≤ λ(G). Both are less than or equal to the minimum degree of the graph, since deleting all neighbors of a vertex of minimum degree will disconnect that vertex from the rest of the graph.Connectivity (graph theory)_item_3_8
• For a vertex-transitive graph of degree d, we have: 2(d + 1)/3 ≤ κ(G) ≤ λ(G) = d.Connectivity (graph theory)_item_3_9
• For a vertex-transitive graph of degree d ≤ 4, or for any (undirected) minimal Cayley graph of degree d, or for any symmetric graph of degree d, both kinds of connectivity are equal: κ(G) = λ(G) = d.Connectivity (graph theory)_item_3_10

## Other properties Connectivity (graph theory)_section_8

Connectivity (graph theory)_unordered_list_4

• Connectedness is preserved by graph homomorphisms.Connectivity (graph theory)_item_4_11
• If G is connected then its line graph L(G) is also connected.Connectivity (graph theory)_item_4_12
• A graph G is 2-edge-connected if and only if it has an orientation that is strongly connected.Connectivity (graph theory)_item_4_13
• Balinski's theorem states that the polytopal graph (1-skeleton) of a k-dimensional convex polytope is a k-vertex-connected graph. Steinitz's previous theorem that any 3-vertex-connected planar graph is a polytopal graph (Steinitz theorem) gives a partial converse.Connectivity (graph theory)_item_4_14
• According to a theorem of G. A. Dirac, if a graph is k-connected for k ≥ 2, then for every set of k vertices in the graph there is a cycle that passes through all the vertices in the set. The converse is true when k = 2.Connectivity (graph theory)_item_4_15