Connectivity

Prove Theorem 2.1: Every walk in a graph between $v$ and $w$ contains a path between $v$ and $w$, and every directed walk from $v$ to $w$ in a digraph contains a directed path from $v$ to $w$.

Prove Theorem 2.2: If $A$ is the adjacency matrix of a simple graph $G=(V, E)$, where $V= \left\{ 1,2, \ldots , n\right\}$, the $(i-j)$ entry in the $k$ th power of $A$ is the number of different walks of length $k$ between the vertices $i$ and $j$. In particular, the $(i-i)$ diagonal entry in $A^{2}$ is the degree of vertex $i$ for each $i$. (See Solved Problem 2.2.)

If the edges in a graph are labeled $e_{i}(i=1,2, \ldots , m)$ and the set of paths between two vertices $v$ and $w$ are labeled $p_{i}(i=1,2, \ldots , k)$, the $\mathbf{v}, \mathbf{w}$ path matrix is the $k \times m$ binary matrix $P_{u v}$ in which the $(i, j)$ entry corresponding to the path $p_{i}$ is 1 if $p_{i}$ contains the edge $e_{j}$ and 0 otherwise. Obtain a path matrix between vertices 1 and 3 in Fig. 2-2.

Let $B$ be the incidence matrix of the simple graph $G=(V, E)$ in which $V=\left\{ 1,2, \ldots , n\right\} , E= \left\{ e_{1}, e_{2}, \ldots , e_{m}\right\}$, and the paths between vertex $i$ and vertex $j$ are labeled $p_{1}, p_{2}, \ldots , p_{k}$. If $P$ is the $(i, j)$ path matrix, the (binary) product $B P^{T}$ is the binary matrix $S$ in which the only nonzero entries are those in the $i$ th and $j$ th rows. (Multiplication of binary matrices here is $\bmod 2$.)

Verify the assertion in Problem 2.4 by considering a path matrix in Fig. 2-2.

If the edge set in a simple graph is labeled $E=\left\{ e_{1}, e_{2}, \ldots , e_{m}\right\}$ and the set of cycles is labeled $\left\{ C_{1}, C_{2}, \ldots , C_{k}\right\}$, the cycle matrix of the graph is the $k \times m$ binary matrix $C$ defined as follows. In the row corresponding to the $i$ th cycle $C_{i}$, the $(i, j)$ entry is 1 if and only if $e_{j}$ is an edge in $\mathrm{C}_{i}$. Obtain a cycle matrix of the graph of Fig. 2-3.

Let $B$ be the incidence matrix of the simple graph $G=(V, E)$, where $V=\left\{ 1,2, \ldots , n\right\} , E= \left\{ e_{1}, e_{2}, \ldots , e_{m}\right\}$, and the cycles in $G$ are labeled $C_{1}, C_{2}, \ldots , C_{k}$. If $C$ is the $k \times m$ cycle matrix, the (binary) matrix product $B C^{T}$ and the (binary) matrix product $C B^{T}$ are zero matrices. (Multiplication of binary matrices here is $\bmod 2$.)

Verify the assertion of Problem 2.7 by considering the cycle matrix in Fig. 2-3.

Show that a graph $G$ is bipartite if and only if every component of $G$ is bipartite.

Prove Theorem 2.3: A simple graph with three or more vertices is bipartite if and only if it has no odd cycles.

Prove Theorem 2.4: For any graph $G, \kappa (G) \leq \lambda (G) \leq \delta (G)$.

Exhibit a graph for which the inequality established in Problem 2.11 is strict.

A matrix is called a totally unimodular (TU) matrix if the determinant of every square submatrix is either -1 or 0 or 1. Show that each entry in a TU matrix is -1 or 0 or 1 but that the converse is not true.

Show that the matrix $A=\left[a_{i j}\right]$ in which each element is -1 or 0 or 1 is a TU matrix if it satisfies the following two conditions: (i) no column can have more than two nonzero elements, and (ii) it is possible to partition the set $I$ of rows of the matrix into sets $I_{1}$ and $I_{2}$ such that if $a_{i j}$ and $a_{k j}$ are the two nonzero elements in column $j$, row $i$ and row $k$ belong to the same subset of the partition if and only if they are of opposite sign.

Show that the following are both TU matrices:

Show that a graph is bipartite if and only if its incidence matrix is a totally unimodular matrix.

The smallest number of colors needed to color the vertices of a graph such that each vertex gets a unique color and no two adjacent vertices get the same color is called the chromatic number (or vertex chromatic number) of the graph. Show that a graph is bipartite if and only if its chromatic number is two.

Show that the following are equivalent in a simple graph $G$:

Suppose each set in a family of subsets of a finite set is represented as a vertex. Two vertices representing two distinct subsets belonging to the family are joined by an edge if they have at least one element in common. The simple graph thus constructed is called the intersection graph of the family of subsets of the given set. Construct the intersection graph of the family of subsets of the set $X=\left\{ 1,2, \ldots , 10\right\}$ with the family $\left\{ A, B, C, D, E, F\right\}$, where $A=\left\{ 1,3,5,7,9\right\} , B= \left\{ 2,4,6,8,10\right\} , C=\left\{ 1,2,3\right\} , D=\left\{ 4,5,6,8,9\right\} , E=\left\{ 5,6,7,9\right\}$, and $F=\left\{ 4,6,10\right\}$.

Show that every simple graph is (isomorphic to) the intersection graph of a family of subsets of a finite set.

The intersection number $\omega (G)$ of a graph $G$ is the minimum number of elements in a set $X$ such that $G$ is an intersection graph of a family of subsets of $X$. Show that the intersection number of a connected graph cannot exceed its size.

Construct:

Show that the intersection number of a connected graph with at least four vertices is equal to its size if and only if it has no triangles.

Find the intersection number of $K_{n}$, where $n>1$.

The intersection graph of a finite family of open intervals of the real line is called an interval graph. Show that the cyclic graph with $n$ vertices is (isomorphic to) an interval graph only when $n=3$.

Show that:

A graph $G$ is called a chordal graph if in every cycle $C$ in $G$ there is an edge (belonging to $G$ ) joining two nonadjacent (in $C$ ) vertices. Show that every interval graph is a chordal graph.

Show that a graph $G$ is chordal if and only if $C_{n}$ is not an induced subgraph of $G$ for any $n>3$.

Give an example of a chordal graph that is not an interval graph.

The graph $G=(V, E)$ is called an indifference graph if for every positive number $\delta$, there exists a mapping $f$ from $V$ to the set of real numbers such that $\left|f(v)-f(w)\right|<\delta$ if and only if $v$ and $w$ are adjacent. Show that the graph in Fig. 2-14 is an indifference graph.

Fig. 2-14

Show that every indifference graph is an interval graph.

By constructing an example, show that an interval graph need not be an indifference graph.

Show that every indifference graph is an interval graph, every interval graph is a chordal graph, and every chordal graph is an intersection graph.

An interval graph is called a unit interval graph if the length of the open interval that corresponds to a vertex is the same for every vertex. Show that a graph is an indifference graph if and only if it is a unit interval graph.

A digraph $D$ is a transitive digraph if there is an arc from $u$ to $v$ whenever there is an arc from $u$ to $w$ and there is an arc from $w$ to $v$ for any set of three distinct vertices $u, v$, and $w$ in $D$. A simple graph $G$ is a transitively orientable graph (or a comparability graph) if $G$ has an orientation $D$ that is a transitive digraph. Show that the complement of an interval graph is a transitively orientable graph.

Obtain a transitive orientation for the complement of the interval graph $K_{1,3}$.

Show that if the complement of $G$ is transitively orientable, it is not necessary that $G$ is an interval graph by constructing an example.

Suppose $G=(V, E)$ is a simple graph with at least one edge. The line graph $\boldsymbol {L}(\boldsymbol {G})$ (also known as the interchange graph, adjoint graph, derived graph, or edge graph) of $G$ is the graph $(W, F)$, where there is a one-to-one correspondence $\phi$ from $E$ to $W$ such that there is an edge between $\phi (e)$ and $\phi \left(e^{\prime }\right)$ if and only if the edges $e$ and $e^{\prime }$ have a vertex in common. Construct the line graph of the graph of $K_{4}$.

Find the line graph of the graph shown in Fig. 2-18(a).

Show that the line graph of $G=(V, E)$ is the intersection graph of a family of subsets of the product set $V \times V$.

If $v$ is the vertex in the line graph $L(G)$ that corresponds to the edge joining vertex $x$ and vertex $y$ in $G$, find the degree of $v$ in $L(G)$.

Find the order and size of $L\left(K_{n}\right)$.

Find the order and size of the line graph $L(G)$ of a simple graph $G$ with $n$ vertices and $m$ edges.

Suppose $G$ is a simple graph with five vertices with degrees $1,2,3,3$, and 3. Find the number of vertices and edges in $L(G)$.

Find the line graph of:

Show that there is no graph $G$ such that $L(G)=K_{1.3}$.

Construct an example to show that if $L(G)$ and $L(H)$ are isomorphic, it is not necessary that $G$ and $H$ are isomorphic.

Show that:

Let $X$ be the set of all the vertices and edges of a graph $G$ with $n$ vertices and $m$ edges. Construct a graph $T(G)=(X, F)$ in which two elements $x$ and $y$ are joined by an edge if:

Show that a graph is a tree if and only if there is a unique path between every pair of vertices in the graph.

Show that a graph is a tree if and only if it is connected and every edge in it is a bridge.

Show that a graph with $n$ vertices is a tree if and only if it is connected and has $(n-1)$ edges.

Show that a graph with $n$ vertices is a tree if and only if it is acyclic and has $(n-1)$ edges.

Show that a graph $G$ is a tree if and only if it is acyclic and whenever any arbitrary two vertices in $G$ are joined by an edge, the resulting enlarged graph $G^{\prime }$ has exactly one cycle.

Show that a graph $G$ is a tree if and only if it is connected and whenever any two arbitrary vertices in $G$ are joined by an edge, the resulting enlarged graph $G^{\prime }$ has exactly one cycle.

Prove Theorem 2.5: The following are equivalent in a graph $G$ with $n$ vertices.

1. $G$ is a tree.

2. There is a unique path between every pair of vertices in $G$.

3. $G$ is connected, and every edge in $G$ is a bridge.

4. $G$ is connected, and it has $(n-1)$ edges.

5. $G$ is acyclic, and it has $(n-1)$ edges.

6. $G$ is acyclic, and whenever any two arbitrary nonadjacent vertices in $G$ are joined by an edge, the resulting enlarged graph $G^{\prime }$ has a unique cycle.

7. $G$ is connected, and whenever any two arbitrary nonadjacent vertices in $G$ are joined by an edge, the resulting enlarged graph has a unique cycle.

Prove Theorem 2.7: A graph is connected if and only if it has a spanning tree.

Prove Theorem 2.8: Let $G$ be a simple graph with $n$ vertices. If a spanning subgraph $H$ satisfies any two of the following three properties, it will satisfy the third property also. (i) $H$ is connected. (ii) $H$ has $(n-1)$ edges. (iii) $H$ is acyclic.

Show that if a graph is disconnected, its complement is connected.

A vertex of degree 1 in a graph is called a terminal vertex (or pendant vertex or end-vertex). Show that every tree of order two or more has at least two terminal vertices.

Show that the vector $\mathrm{d}=\left[\begin{array}{llll}d_{1} & d_{2} & \ldots & d_{n}\end{array}\right]$ of positive integers, where $d_{1} \leq d_{2} \leq \ldots \leq d_{n}$ is the degree vector of a tree with $n$ vertices if and only if $d_{1}+d_{2}+\cdots +d_{n}=2(n-1)$.

Prove Theorem 2.6: The center of a tree is either a singleton set consisting of a unique vertex or a set consisting of two adjacent vertices.

A path $P$ between two distinct vertices in a connected graph $G$ is a diametral path if there is no other path in $G$ whose length is more than the length of $P$. Show that:

A tree with exactly one vertex $v$ of degree 2 in which the degree of every nonterminal vertex (other than $v$ ) is 3 is called a binary tree, and the root of the binary tree is the unique vertex of degree 2. Show that the number of vertices in a binary tree is odd.

Show that the number of terminal vertices in a binary tree with $n$ vertices is $(n+1) / 2$.

Show that if $T$ is a tree with $n$ vertices and $G$ is a graph with $\delta (G) \geq (n-1), T$ is isomorphic to a subgraph of $G$.

Show that a tree with $n$ vertices is isomorphic to a subgraph of the complement of the cyclic graph with $(n+2)$ vertices.

A graph is said to be a unicyclic graph if it has exactly one cyclic subgraph. Show that if any two of the following conditions are satisfied in a graph with $n$ vertices and $m$ vertices, the third condition also is satisfied:

Show that each labeled tree with $n$ vertices corresponds to a unique vector $s=\left[\begin{array}{llll}s_{1} & s_{2} & \cdots & s_{n-2}\end{array}\right]$, where $s_{i} \in N=\left\{ 1,2, \ldots , n\right\}$ for $i=1,2, \ldots ,(n-2)$.

Find the unique vector corresponding to the labeled tree shown in Fig. 2-19.

Fig. 2-19

Show that every vector $s$ with $(n-2)$ components, where each component is an element of $N= \left\{ 1,2, \ldots , n\right\}$, corresponds to a unique labeled tree with $n$ vertices.

Obtain the unique labeled tree corresponding to the vector $s=\begin{array}{llllllllll}1 & 4 & 2 & 2 & 4 & 3 & 3 & 3 & 4 & 4\end{array}$ ].

Prove Theorem 2.9 (Cayley's theorem): The number of distinct labeled trees with $n$ vertices is $n^{n-2}$, which is also equal to the number of spanning trees in $K_{n}$

A directed tree $T$ such that there is a unique vertex $v$ of indegree zero and that the indegree of every other vertex is 1 is called an arborescence rooted at $v$. Find the number of distinct labeled arborescences with $n$ vertices.

A tree with $n$ vertices is an edge-labeled tree if each edge is assigned a unique positive integer between 1 and $(n-1)$. Show that the number of distinct edge-labeled trees with $(n-1)$ labeled edges and $n$ unlabeled vertices is $n^{n-3}$.

Let $G$ be an undirected graph with $n$ labeled vertices and $m$ labeled edges. Assign each edge an arbitrary orientation, and let $A$ be the incidence matrix of the resulting digraph. Show that:

Suppose an arbitrary incidence matrix $A$ of a connected graph $G=(V, E)$ with $n$ vertices is defined as in Problem 2.77. The reduced incidence matrix $\boldsymbol {A}_{r}$ is the matrix obtained from $A$ by deleting a row, say the $n$th row. Show that any $(n-1) \times (n-1)$ submatrix $B$ of matrix $A_{r}$ is nonsingular if and only if the edges corresponding to the columns of $B$ constitute the edges of a spanning tree in $G$.

Show that if $A_{r}$ is the reduced incidence matrix (as defined in Problem 2.77) of a connected graph $G$ and if $\left(A_{r}\right)^{T}$ is its transpose, the number of spanning trees in $G$ is equal to the determinant of $A_{r}\left(A_{r}\right)^{T}$.

If $e$ is an edge in graph $G, G-e$ is the subgraph of $G$ obtained from $G$ by deleting $e$ from $G$. After edge $e$ joining the vertices $v$ and $w$ is deleted, suppose the vertices $v$ and $w$ are merged to constitute a single vertex. The resulting graph $G^{\prime }$ is called the contracted graph obtained by contracting edge $e$ and is denoted by G.e. If $\tau (G)$ is the number of spanning trees in $G$, show that $\tau (G)=\tau (G-e)+ \tau$ (G.e).

Show that if $T_{i}=\left(V_{i}, E_{i}\right)$, where $i=1,2, \ldots , k$ are subtrees of $T=(V, E)$ such that every pair of subtrees have at least one vertex in common, the entire set of subtrees have a vertex in common.

Obtain a DFS spanning tree starting the search from vertex 2 in the graph shown in Fig. 2-20.

Fig. 2-20

Show that a digraph $G=(V, E)$ is strongly connected if and only if the following property is satisfied: For every nonempty subset $X$ of vertices, there exists an arc from a vertex $x$ in $X$ to a vertex $y$ in the complement of $X$.

Show that if a tournament has a directed circuit, it has a directed triangle.

If $G$ is a tournament with $n$ vertices, the vector whose components are the $n$ outdegrees arranged in a nondecreasing order is called the score vector of the tournament. A tournament is a transitive tournament if whenever $(u, v)$ and $(v, w)$ are arcs, $(u, w)$ is also an arc. Show that a tournament $G$ with $n$ vertices is transitive if and only if its score vector is $\left[\begin{array}{lllll}0 & 1 & 2 & \cdots & (n-1)\end{array}\right]$.

Suppose $D^{\prime }$ is the digraph obtained from a strongly connected mixed graph $G$ (see Section 2.2) by deleting an undirected edge $e=\left\{ x, y\right\}$ from $G$ and replacing every other edge in $G$ by two arcs in opposite directions. Let $X$ be the set of all vertices $v$ such that there is a directed path in $D^{\prime }$ from $x$ to $v$ consisting of at least one arc. Likewise, let $Y$ be the set of all vertices $v$ such that there is a direct path in $D^{\prime }$ from $y$ to $v$ consisting of at least one arc. If $x$ is not in $Y$ and $y$ is not in $X, e=\left\{ x, y\right\}$ is a bridge in the mixed graph.

Show that if $G$ is a strongly connected mixed graph, it is possible to convert any edge that is not a bridge into an arc such that the resulting mixed graph is also strongly connected.

Prove Theorem 2.10 (Robbins's theorem): A graph is strongly orientable if and only if it is connected and has no bridges.

Suppose $G$ is a connected graph in which no edge is a bridge, and let $T$ be the DFS spanning (directed) tree obtained by starting the search from a fixed vertex $r$ called the root of the tree. Show that there is a directed path in $T$ to every vertex from root $r$.

Let $G$ be a connected simple graph in which no edge is a bridge, and let $T$ be a DFS spanning tree in the graph. Assume that $f(x)$ is the unique label of vertex $x$ assigned to it during the search, as in Problem 2.88. If $\left\{ v, u\right\}$ is any edge that is not used as an arc in $T$ and if $w$ is any vertex such that $f(v)< f(w) \leq f(u)$, there is a directed path in $T$ from $v$ to $w$.

Suppose $G$ and $T$ are as in Problem 2.89. If there is a directed path $P$ in $T$ from vertex $a$ to vertex $x$ and a directed path $Q$ in $T$ from another vertex $b$ to $x$, either there is a directed path from $a$ to $b$ or from $b$ to $a$ in tree $T$.

Suppose $G$ and $T$ are as in Problem 2.89 with the same labeling as before. If $\left\{ u, v\right\}$ is an edge not in $T$ and if $f(u)<f(v)$, the edge is converted into an arc from $v$ to $u$. Thus each edge in $G$ is now converted into an arc, giving an orientation $G^{\prime }$ of graph $G$ based on the depth first search. The length of the (unique) path in $T$ from the root to vertex $x$ is denoted by $d(x)$. If $d(x) \geq 1$ and $y$ is any vertex with $d(y)<d(x)$, there is a directed path in $G^{\prime }$ from $x$ to $y$.

Let $G$ and $G^{\prime }$ be as in Problem 2.91. Show that there is a directed path in $G^{\prime }$ from every vertex to the root.

Prove Theorem 2.11 (Roberts's theorem): The orientation procedure using the depth first search in a connected graph with no bridges yields a strongly connected digraph. (This is another way of establishing Robbins's theorem. Thus the proof given here may be called Roberts's proof of Robbins's theorem.)

Show that a vertex $\nu$ of a connected graph is a cut vertex if and only if there exist two distinct vertices $u$ and $w$ such that every path between these two vertices passes through $v$.

Show that any nontrivial graph has at least two vertices that are not cut vertices.

Show that an edge of a connected graph is a bridge if and only if there exist vertices $\nu$ and $w$ such that every path between these two vertices contains this edge.

Show that an edge is a bridge if and only if no cycle contains that edge.

A nontrivial connected graph is called a nonseparable graph if it has no cut vertices. A subgraph $H$ of a graph $G$ is a block in graph $\boldsymbol {G}$ if $H$ is nonseparable and maximal with respect to this property: If there is a nonseparable subgraph $H^{\prime }$ such that $H$ is a subgraph of $H^{\prime }, H=H^{\prime }$. Obtain the blocks of the graph in Fig. 2-21.

Fig. 2-21

Show that two blocks have at most one vertex in common. What distinguishing feature does a vertex common to two blocks have?

Show that $G$ is 2-connected if and only if $G$ is connected with at least three vertices but no cut vertices.

Show that the center of a connected graph is a subset of the set of vertices of a block.

Show that in a graph with $n$ vertices, the length of a path cannot exceed $(n-1)$ and the length of a cycle cannot exceed $n$.

Show that a graph $G$ with $n$ vertices is connected if and only if no entry in $(A+A^{2}+\cdots +A^{n-1})$ is zero, where $A$ is its adjacency matrix.

Show that the sum of the diagonal elements of the second power of the adjacency matrix is twice the number of edges of the graph.

Find the intersection number for $K_{n}$ when $n>4$.

Let $T(G)$ be the total graph of the graph $G=(V, E)$, where $V=\left\{ 1,2, \ldots , n\right\}$. Let $d_{i}$ be the degree of $i$ in $G$

If both $G$ and its complement are trees, find the order of $G$.

Find the number of edges in a forest with $n$ vertices and $k$ trees.

Show that a tree is a bipartite graph.

Show that if a tree has exactly two terminal vertices, the degree of every other vertex is 2 and thus it is a path.

Find the number of terminal vertices in a tree with $n$ vertices.

Show that if the degree of every nonterminal vertex in a tree is 3, the number of vertices in the tree is even.

In a tree with 14 terminal vertices, the degree of every nonterminal vertex is either 4 or 5. Find the number of vertices of degree 4 and of degree 5.

Find the number of distinct labeled trees with five vertices.

If $G$ is the subgraph obtained by deleting an edge from $K_{n}$, find the number of spanning trees in $G$.

Show that a bipartite graph is a transitively orientable graph but not conversely.