91Ó°ÊÓ

a) How many paths of length 5 are there in the complete bipartite graph \(K_{3,7}\) ? (Remember that a path such as \(v_{1} \rightarrow v_{2} \rightarrow v_{3} \rightarrow v_{4} \rightarrow v_{5} \rightarrow v_{6}\) is considered to be the same as the path \(\left.v_{6} \rightarrow v_{5} \rightarrow v_{4} \rightarrow v_{3} \rightarrow v_{2} \rightarrow v_{1} .\right)\) b) How many paths of length 4 are there in \(K_{3,7}\) ? c) Let \(m, n, p \in \mathbf{Z}^{+}\)with \(2 m

a) For \(n \geq 3\), how many different Hamilton cycles are there in the complete graph \(K_{n}\) ? b) How many edge-disjoint Hamilton cycles are there in \(K_{21} ?\) c) Nineteen students in a nursery school play a game each day where they hold hands to form a circle. For how many days can they do this with no student holding hands with the same playmate twice?

a) How many paths of length 4 are there in the complete graph \(K_{7}\) ? (Remember that a path such as \(v_{1} \rightarrow v_{2} \rightarrow\) \(v_{3} \rightarrow v_{4} \rightarrow v_{5}\) is considered to be the same as the path \(\left.v_{5} \rightarrow v_{4} \rightarrow v_{3} \rightarrow v_{2} \rightarrow v_{1} \cdot\right)\) b) Let \(m, n \in \mathbf{Z}^{+}\)with \(m

What is the length of a longest path in each of the following graphs? a) \(K_{1,4}\) b) \(K_{3,7}\) c) \(K_{7,12}\) d) \(K_{m, n}\), where \(m, n \in \mathbf{Z}^{+}\)with \(m

a) Find the number of edges in \(Q_{8}\). b) Find the maximum distance between pairs of vertices in \(Q_{8}\). Give an example of one such pair that achieves this distance. c) Find the length of a longest path in \(Q_{8}\).

a) What is the dimension of the hypercube with 524,288 edges? b) How many vertices are there for a hypercube with \(4,980,736\) edges?

If \(G=(V, E)\) is an undirected graph, a subset \(K\) of \(V\) is called a covering of \(G\) if for every edge \(\\{a, b\\}\) of \(G\) either \(a\) or \(b\) is in \(K\). The set \(K\) is a minimal covering if \(K-\\{x\\}\) fails to cover \(G\) for each \(x \in K\). The number of vertices in a smallest covering is called the covering number of \(G\). a) Prove that if \(I \subseteq V\), then \(I\) is an independent set in \(G\) if and only if \(V-I\) is a covering of \(G\). b) Verify that \(|V|\) is the sum of the independence number of \(G\) (as defined in Exercise 25 for Section 11.5) and its covering number.

Give an example of a connected graph \(G\) where removing any edge of \(G\) results in a disconnected graph.

Prove that for \(n \geq 2\), the hypercube \(Q_{n}\) has a Hamilton cycle.

a) Let \(G\) be an undirected graph with \(n\) vertices. If \(G\) is isomorphic to its own complement \(\bar{G}\), how many edges must \(G\) have? (Such a graph is called self-complementary.) b) Find an example of a self-complementary graph on four vertices and one on five vertices. c) If \(G\) is a self-complementary graph on \(n\) vertices, where \(n>1\), prove that \(n=4 k\) or \(n=4 k+1\), for some \(k \in \mathbf{Z}^{+}\).