10.4 Connectivity

Question 1

Definition 1:
Paths:

Hints:

What is a circuit?
when is a path or circuit simple?

pass through whom and traverse whom?

Answer 1

Let n be a nonnegative integer and G an undirected graph. A path of length n from u
to v in G is a sequence of n edges e1, … , en of G for which there exists a sequence
x0 = u, x1, … , xn−1, xn = v of vertices such that ei has, for i = 1, … , n, the endpoints xi−1
and xi
. When the graph is simple, we denote this path by its vertex sequence x0, x1, … , xn
(because listing these vertices uniquely determines the path). The path is a circuit if it begins
and ends at the same vertex, that is, if u = v, and has length greater than zero. The path or
circuit is said to pass through the vertices x1, x2, … , xn−1 or traverse the edges e1, e2, … , en.
A path or circuit is simple if it does not contain the same edge more than once.

Question 2

when it is not necessary to distinguish btween multiple edges then how can u denote a path:

vertices and zero length ?

Answer 2

we will denote a path
e1, e2, … , en, where ei is associated with {xi−1, xi
} for i = 1, 2, … , n by its vertex sequence
x0, x1, … , xn.
This notation identifies a path only as far as which vertices it passes through.

Consequently, it does not specify a unique path when there is more than one path that passes
through this sequence of vertices, which will happen if and only if there are multiple edges between some successive vertices in the list. Note that a path of length zero consists of a single
vertex.

Question 3

Walk :

simple path?

and in this case path is?

Answer 3

the term walk is used instead of path,
where a walk is defined to be an alternating sequence of vertices and edges of a graph,
v0, e1, v1, e2, … , vn−1, en, vn, where vi−1 and vi are the endpoints of ei for i = 1, 2, … , n. When
this terminology is used, Closed Walk is used instead of circuit to indicate a walk that begins and
ends at the same vertex.

trail is used to denote a walk that has no repeated edge (replacing
the term simple path).

When this terminology is used, the terminology path is often used for
a trail with no repeated vertices, conflicting with the terminology in Definition 1.

Question 4

Path definition Directed graphs:

Answer 4

Let n be a nonnegative integer and G a directed graph. A path of length n from u to v in G is
a sequence of edges e1, e2, … , en of G such that e1 is associated with (x0, x1), e2 is associated
with (x1, x2), and so on, with en associated with (xn−1, xn), where x0 = u and xn = v. When
there are no multiple edges in the directed graph, this path is denoted by its vertex sequence
x0, x1, x2, … , xn. A path of length greater than zero that begins and ends at the same vertex
is called a circuit or cycle. A path or circuit is called simple if it does not contain the same
edge more than once.

Note that the terminal vertex of an edge in a path is the initial vertex of the next edge in the
path.

Question 5

Paths in Acquaintanceship Graphs

the conjecture here?

Answer 5

Many social scientists have conjectured that almost every
pair of people in the world are linked by a small chain of people, perhaps containing just five or
fewer people. This would mean that almost every pair of vertices in the acquaintanceship graph
containing all people in the world is linked by a path of length not exceeding four.

Question 6

Paths in Collaboration Graphs

Answer 6

Erdos number ˝ of a person m (defined in terms of
relations in Supplementary Exercise 14 in Chapter 9) is the length of the shortest path between
m and the extremely prolific mathematician Paul Erdos (who died in 1996).

Bacon number:
Kevin Bacon remarked that he had worked with everyone in Hollywood or
someone who worked with them. This led some people to invent a party game where participants
where challenged to find a sequence of movies leading from each actor named to Kevin Bacon.

Question 7

Connected and disconnected undirected graph?

How to disconnect a graph.

Answer 7

An undirected graph is called connected if there is a path between every pair of distinct
vertices of the graph. An undirected graph that is not connected is called disconnected. We
say that we disconnect a graph when we remove vertices or edges, or both, to produce a
disconnected subgraph.

Question 8

Theorem 1:

of paths in undirected connected graph:

Answer 8

There is a simple path between every pair of distinct vertices of a connected undirected graph.

prove it:

Let u and v be two distinct vertices of the connected undirected graph G = (V, E). Because G is connected, there is at least one path between u and v. Let x0, x1, … , xn, where x0 = u
and xn = v, be the vertex sequence of a path of least length. This path of least length is simple.
To see this, suppose it is not simple. Then xi = xj for some i and j with 0 ≤ i < j. This means
that there is a path from u to v of shorter length with vertex sequence x0, x1, … , xi−1, xj
, … , xn
obtained by deleting the edges corresponding to the vertex sequence xi
, … , xj−1.

Question 9

CONNECTED COMPONENTS :

need to comprehend!!

Answer 9

A connected component of a graph G is a connected subgraph of G that is not a proper subgraph of another connected subgraph of G. That is, a connected
component of a graph G is a maximal connected subgraph of G. A graph G that is not connected has two or more connected components that are disjoint and have G as their union.

Question 10

Cut vertices or Articulation points:

Answer 10

Sometimes the removal from a graph of a vertex and all incident edges produces a subgraph
with more connected components. Such vertices are called cut vertices(or articulation points).

Question 11

Cut edge or bridge :

Answer 11

The removal of a cut vertex from a connected graph produces a subgraph that is not connected.
Analogously, an edge whose removal produces a graph with more connected components than
in the original graph is called a cut edge or bridge.

Question 12

Non seperable graphs and example :

Answer 12

Not all graphs have cut vertices. For example, the complete
graph Kn, where n ≥ 3, has no cut vertices. When you remove a vertex from Kn and all edges
incident to it, the resulting subgraph is the complete graph Kn−1, a connected graph. Connected
graphs without cut vertices are called nonseparable graphs, and can be thought of as more connected than those with a cut vertex.

Question 13

Vertex Cut

hint:

or sperating set

Answer 13

A subset V′ of the vertex set V of G = (V, E) is a vertex cut, or separating set, if G − V′
is disconnected.

Question 14

vertex connectivity :

What if graph is complete?

definition only

Answer 14

We define the vertex connectivity
of a noncomplete graph G, denoted by 𝜅(G), as the minimum number of vertices in a vertex cut.

When G is a complete graph, it has no vertex cuts, because removing any subset of its
vertices and all incident edges still leaves a complete graph. Consequently, we cannot define 𝜅(G) as the minimum number of vertices in a vertex cut when G is complete. Instead,
we set 𝜅(Kn) = n − 1, the number of vertices needed to be removed to produce a graph with a
single vertex

Consequently, for every graph G, 𝜅(G) is minimum number of vertices that can be removed from G to either disconnect G or produce a graph with a single vertex.

Question 15

Limits on Connectivity:

Vertex Connectivity.

Answer 15

0 ≤ 𝜅(G) ≤ n − 1 if G has n vertices, 𝜅(G) = 0 if and only if G is disconnected or G = K1,
and 𝜅(G) = n − 1 if and only if G is complete

Question 16

What can connectivity tells us about the graph?

Answer 16

The larger 𝜅(G) is, the more connected we consider G to be. Disconnected graphs and K1
have 𝜅(G) = 0, connected graphs with cut vertices and K2 have 𝜅(G) = 1, graphs without cut
vertices that can be disconnected by removing two vertices and K3 have 𝜅(G) = 2, and so
on.

Question 17

K- connected ?

Answer 17

We say that a graph is k-connected (or k-vertex-connected), if 𝜅(G) ≥ k.
A graph G is
1-connected if it is connected and not a graph containing a single vertex; a graph is 2-connected,
or biconnected, if it is nonseparable and has at least three vertices. Note that if G is a kconnected graph, then G is a j-connected graph for all j with 0 ≤ j ≤ k.

Question 18

Edge Cut:

Answer 18

We can also measure the connectivity of a connected graph G =
(V, E) in terms of the minimum number of edges that we can remove to disconnect it. If a graph
has a cut edge, then we need only remove it to disconnect G. If G does not have a cut edge, we
look for the smallest set of edges that can be removed to disconnect it. A set of edges E′ is called
an edge cut of G if the subgraph G − E′ is disconnected.

Question 19

Edge connectivity

Answer 19

The edge connectivity of a graph G, denoted by 𝜆(G), is the minimum number of edges in an edge cut of G.
This defines 𝜆(G) for
all connected graphs with more than one vertex because it is always possible to disconnect
such a graph by removing all edges incident to one of its vertices.

Question 20

limits on Edge connectivity :

and what magnitude implies what:

Answer 20

Note that 𝜆(G) = 0 if G is
not connected or has a single vertex.
It follows that if G is a graph with n vertices, then 0 ≤ 𝜆(G) ≤ n − 1.
𝜆(G) = n − 1 where G is a graph with n vertices if and only if
G = Kn, which is equivalent to the statement that 𝜆(G) ≤ n − 2 when G is not a complete graph.

Question 21

AN INEQUALITY FOR VERTEX CONNECTIVITY AND EDGE CONNECTIVITY:

Answer 21

𝜅(G) ≤ 𝜆(G) ≤ minv∈V deg(v).

When G = (V, E) is a noncomplete connected graph with at least three vertices, the minimum
degree of a vertex of G is an upper bound for both the vertex connectivity of G and the edge
connectivity of G
As : deleting all the neighbors of a fixed vertex of minimum degree disconnects G, and
deleting all the edges that have a fixed vertex of minimum degree as an endpoint disconnects G.

In Exercise 55, we ask the reader to show that 𝜅(G) ≤ 𝜆(G) when G is a connected noncomplete graph. Note also that 𝜅(Kn) = 𝜆(Kn) = minv∈V deg(v) = n − 1 when n is a positive
integer and that 𝜅(G) = 𝜆(G) = 0 when G is a disconnected graph.

Question 22

APPLICATIONS OF VERTEX AND EDGE CONNECTIVITY

Answer 22

Graph connectivity plays an

important role in many problems involving the reliability of networks.

Question 23

Strongly connected Directed graph :

Answer 23

A directed graph is strongly connected if there is a path from a to b and from b to a whenever
a and b are vertices in the graph.

Question 24

Weakly connected directed graph:

Answer 24

A directed graph is weakly connected if there is a path between every two vertices in the
underlying undirected graph.

strongly connected
directed graph is also weakly connected.

Question 25

STRONG COMPONENTS OF A DIRECTED GRAPH

Answer 25

The subgraphs of a directed graph G
that are strongly connected but not contained in larger strongly connected subgraphs, that is,
the maximal strongly connected subgraphs, are called the strongly connected components or
strong components of G.

Note that if a and b are two vertices in a directed graph, their strong
components are either the same or disjoint. (We leave the proof of this last fact as Exercise 17.)

Question 26

Paths and Isomorphism

Answer 26

The existence of a simple circuit of a particular length is a useful invariant
that can be used to show that two graphs are not isomorphic. In addition, paths can be used to
construct mappings that may be isomorphisms.
circuit length >2
proof, ex 60.

We can also use paths to find
mappings that are potential isomorphisms.

Question 27

Counting Paths Between Vertices

theorem 2

The number of paths between two vertices in a graph can be determined using its adjacency
matrix.

prove it.

Answer 27

Let G be a graph with adjacency matrix A with respect to the ordering v1, v2, … , vn of the
vertices of the graph (with directed or undirected edges, with multiple edges and loops allowed).

The number of different paths of length r from vi to vj
, where r is a positive integer,
equals the (i, j)th entry of A^r.

Theorem 2 can be used to find the length of the shortest path between two vertices of a
graph (see Exercise 56), and it can also be used to determine whether a graph is connected (see
Exercises 61 and 62).