Chapter 6

Prove that a graph \(G\) is connected if and only if \(G\) contains a spanning tree.

Prove that a directed graph \(D=(V, E)\) is strongly connected if and only if for any partition \(V_{1}, V_{2}\) of \(V\) there is an edge \((x, y)\) with \(x \in V_{1}\) and \(y \in V_{2}\).

Prove that \(Q_{n}\) where \(n\) is some integral power of 2 has \(2^{n}\) vertices and \(n \cdot 2^{n-1}\) edges.

Find a directed graph that is not Eulerian but for which the underlying graph is Eulerian.

Prove that \(Q_{n}\) is bipartite for \(n=2,3,4, \ldots\)

Prove that for any graph \(G\) on six vertices, either \(G\) or \(G\) contains a triangle.

Devise an algorithm to find an Eulerian circuit in a directed graph, if one exists. Modify the algorithm to find all Eulerian circuits in a graph.

Challenge: A complete directed graph is a directed graph whose underlying graph is a complete graph. Show that the sum of the squares of the indegrees over all vertices is equal to the sum of the squares of the outdegrees over all vertices in any directed complete graph.

A university has eight buildings that need to be connected so that each building's computer network is accessible to the networks in the other buildings. The distance between buildings is given in units of 1000 yards. These distances between buildings are given in the table that follows. The distance from building \(i\) to building \(j\) is the same as the distance from building \(j\) to building \(i .\) $$\begin{array}{c|c|c|c|c|c|c|c|c|} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\\\\hline 1 & \- & 1.6 & 1.4 & 0.5 & 1.2 & 1.5 & 1.8 & 2.3 \\\2 & & \- & 0.9 & 1.8 & 1.2 & 2.6 & 2.3 & 1.1 \\\3 & & & \- & 2.6 & 1.7 & 2.5 & 1.9 & 1.0 \\\4 & & & & \- & 0.7 & 1.6 & 1.5 & 0.9 \\\5 & & & & & \- & 0.9 & 1.1 & 0.8 \\\6 & & & & & & \- & 0.6 & 1.0 \\\7 & & & & & & & \- & 0.5 \\\8 & & & & & & & & \- \\\\\hline\end{array}$$ Which pairs of buildings should be directly connected to connect all the buildings with a minimum total network length? What is the length of a minimum network? What are the different possible minimum networks?

Let \(G=(V, E)\) be a graph. Prove that if the minimum degree of \(G\) is greater than \((|V|-1) / 2,\) then \(G\) is connected.