Chapter 8

Can there be a 3-regular graph with five vertices?

Determine if each complete bipartite graph \(K_{m, n}\) is Hamiltonian. If a graph is not Hamiltonian, does it contain a Hamiltonian path? $$K_{2,4}$$

Determine if each complete bipartite graph \(K_{m, n}\) is Hamiltonian. If a graph is not Hamiltonian, does it contain a Hamiltonian path? $$K_{3,4}$$

The complement of simple graph \(G\) is a simple graph \(G^{\prime}\) containing all vertices in \(G ;\) two vertices are adjacent in \(G^{\prime}\) if they are not adjacent in \(G .\) For example, the graphs in Figures 8.32 and 8.33 are complements of each other. Find the complements of the graphs.

Let \(n\) and \(e\) denote the numbers of vertices and edges in a simple graph \(G\) and \(e^{\prime}\) the number of edges in \(G^{\prime} .\) How are \(e\) and \(e^{\prime}\) related?

Give an example of a graph that is: Both Eulerian and Hamiltonian.

Give an example of a graph that is: Eulerian, but not Hamiltonian.

Give an example of a graph that is: Hamiltonian, but not Eulerian.

Give an example of a graph that is: Neither Eulerian nor Hamiltonian.

Display a Hamiltonian cycle for the 4-cube.

A company wishes to schedule 1 -hour meetings beginning at 7 \(\mathrm{AM}\) . between every two of its six regional managers-A, B, C, D, and \(\mathrm{F}-\) so each can spend an hour with each of the other five for better acquaintance. Find the various possible schedule pairings. (This is a round-robin tournament in disguise.) (S. W. Golomb, 1993)

Five basketball teams, \(a\) through \(e,\) enter a round-robin tournament. Create a schedule so that every team plays every other team exactly once. (Hint: since the number of teams is odd, add a dummy team \(x\). If a team is paired with \(x,\) the team draws a bye in that round.)

Show that any simple graph with two or more vertices has at least two vertices of the same degree. (Hint: Use the pigeonhole principle.)

Let \(v_{1}, \ldots, v_{n}\) be n vertices with degrees \(\operatorname{deg}\left(v_{1}\right), \ldots, \operatorname{deg}\left(v_{n}\right),\) respectively, such that \(\sum_{i=1}^{n} \operatorname{deg}\left(v_{i}\right)\) is even. Prove that there exists a graph satisfying these conditions. [Hint: Let \(\sum_{i=1}^{n} \operatorname{deg}\left(v_{i}\right)=2 e .\) Use induction on e. \(]\)

Let \(v_{1}, \ldots, v_{n}\) be \(\mathrm{n}\) vertices with degrees \(\operatorname{deg}\left(v_{1}\right), \ldots, \operatorname{deg}\left(v_{n}\right),\) respectively, such that \(\sum_{i=1}^{n} \operatorname{deg}\left(v_{i}\right)\) is even. Prove that there exists a graph satisfying these conditions. [Hint: Let \(\left.\sum_{i=1}^{n} \operatorname{deg}\left(v_{i}\right)=2 e . \text { Use induction on } e .\right]\)

A power cycle of order \(n\) is a cyclic permutation of the first \(n(\geq 2)\) positive integers such that the sum of every pair of adjacent elements is a power. Find a power cycle of order 17.

Write an algorithm to determine if a connected graph is Eulerian, using its adjacency list representation.

Write an algorithm to determine if a connected graph contains an Eulerian path, using its adjacency matrix.