Chapter 9

Estimate the number of vertices and edges in each of the following graphs. Would the graph be considered sparse, so that an adjacency matrix would be inefficient? (a) Vertices: Cities of the world that are served by at least one airline. Edges: Pairs of cities that are connected by a regular direct flight. (b) Vertices: ASCII characters. Edges: connect characters that differ in their binary code by exactly two bits. (c) Vertices: All English words. Edges: An edge connects word \(x\) to word \(y\) if \(x\) is a prefix of \(y\).

Each edge of a graph is colored with one of the four colors red, blue, yellow, or green. How could you represent the edges in this graph using a variation of the adjacency matrix structure?

In a simple undirected graph with no self-loops, what is the maximum number of edges you can have, keeping the graph unconnected? What is the minimum number of edges that will assure that the graph is connected?

Write out the Gray Code for the 4 -cube.

Given the following sets of points in the unit square, find the shortest circuit that visits all the points and find the circuit that is obtained with the strip algorithm. (a) \(\\{(0.1 k, 0.1 k): k=0,1,2, \ldots, 10\\}\) (b) \\{(0.1,0.3),(0.3,0.8),(0.5,0.3),(0.7,0.9),(0.9,0.1)\\} (c) \\{(0.0,0.5),(0.5,0.0),(0.5,1.0),(1.0,0.5)\\} (d) \\{(0,0),(0.2,0.6),(0.4,0.1),(0.6,0.8),(0.7,0.5)\\}

Directed graphs \(G_{1}, \ldots, G_{6},\) each with vertex set \\{1,2,3,4,5\\} are represented by the matrices below. Which graphs are isomorphic to one $$\begin{aligned} &\text { nother }\\\ &G_{1}:\left(\begin{array}{lllll} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \end{array}\right) \quad G_{2}:\left(\begin{array}{lllll} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right) \quad G_{3}:\left(\begin{array}{ccccc} 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{array}\right) \end{aligned}$$ $$ G_{4}:\left(\begin{array}{lllll} 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right) \quad G_{5}:\left(\begin{array}{lllll} 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \end{array}\right) \quad G_{6}:\left(\begin{array}{lllll} 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{array}\right) $$

In the NCAA final-four basketball tournament, the East champion plays the West champion, and the champions from the Mideast and Midwest play. The winners of the two games play for the national championship. Draw the eight different single-elimination tournament graphs that could occur.

Prove that if an undirected graph has a subgraph that is a \(K_{3}\) it then its chromatic number is at least \(3 .\)

What is the maximum number of edges in an undirected graph with eight vertices?

What is \(\chi\left(K_{n}\right), n \geq 1 ?\)

(a) How many edges does a complete tournament graph with \(n\) vertices have? (b) How many edges does a single-elimination tournament graph with \(n\) vertices have?

Prove (by induction on \(k\) ) that if the relation \(r\) on vertices of a graph is defined by vrw if there is an edge connecting \(v\) to \(w\), then \(r^{k}, k \geq 1,\) is defined by \(v r^{k} w\) if there is a path of length \(k\) from \(v\) to \(w\).

Draw complete undirected graphs with \(1,2,3,4,\) and 5 vertices. How many edges does a \(K_{n},\) a complete undirected graph with \(n\) vertices, have?

For each of the following distance matrices of graphs, identify the diameter, radius and center. Assume the graphs vertices are the numbers 1 through \(n\) for an \(n \times n\) matrix. (a) \(\left(\begin{array}{llllllllll}0 & 2 & 1 & 2 & 2 & 3 & 3 & 2 & 1 & 1 \\\ 2 & 0 & 1 & 2 & 3 & 3 & 3 & 2 & 3 & 2 \\ 1 & 1 & 0 & 1 & 2 & 2 & 2 & 1 & 2 & 1 \\ 2 & 2 & 1 & 0 & 3 & 3 & 3 & 2 & 3 & 2 \\ 2 & 3 & 2 & 3 & 0 & 2 & 1 & 1 & 2 & 1 \\ 3 & 3 & 2 & 3 & 2 & 0 & 1 & 1 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 0 & 1 & 3 & 2 \\ 2 & 2 & 1 & 2 & 1 & 1 & 1 & 0 & 2 & 1 \\ 1 & 3 & 2 & 3 & 2 & 3 & 3 & 2 & 0 & 1 \\ 1 & 2 & 1 & 2 & 1 & 2 & 2 & 1 & 1 & 0\end{array}\right)\) (b) \(\left(\begin{array}{llllllllllll}0 & 2 & 2 & 2 & 3 & 3 & 3 & 1 & 2 & 3 & 1 & 1 \\ 2 & 0 & 2 & 2 & 1 & 1 & 1 & 3 & 2 & 1 & 1 & 3 \\ 2 & 2 & 0 & 1 & 3 & 2 & 1 & 2 & 2 & 3 & 1 & 1 \\ 2 & 2 & 1 & 0 & 3 & 1 & 2 & 1 & 2 & 3 & 2 & 1 \\\ 3 & 1 & 3 & 3 & 0 & 2 & 2 & 4 & 3 & 2 & 2 & 4 \\ 3 & 1 & 2 & 1 & 2 & 0 & 2 & 2 & 3 & 2 & 2 & 2 \\ 3 & 1 & 1 & 2 & 2 & 2 & 0 & 3 & 3 & 2 & 2 & 2 \\ 1 & 3 & 2 & 1 & 4 & 2 & 3 & 0 & 3 & 4 & 2 & 2 \\ 2 & 2 & 2 & 2 & 3 & 3 & 3 & 3 & 0 & 1 & 3 & 1 \\ 3 & 1 & 3 & 3 & 2 & 2 & 2 & 4 & 1 & 0 & 2 & 2 \\ 1 & 1 & 1 & 2 & 2 & 2 & 2 & 2 & 3 & 2 & 0 & 2 \\ 1 & 3 & 1 & 1 & 4 & 2 & 2 & 2 & 1 & 2 & 2 & 0\end{array}\right)\)

Prove that the number of vertices in an undirected graph with odd degree must be even. Hint. Prove by induction on the number of edges.

Let \(G=(V, E)\) with \(|V| \geq 11,\) and let \(U\) be the set of all undirected edges between distinct vertices in \(V\). Prove that either \(G\) or \(G^{\prime}=\left(V, E^{c}\right)\) is nonplanar.

(a) Under what conditions will a round-robin tournament graph be Eulerian? (b) Prove that every round-robin tournament graph is Hamiltonian.

Discuss reasons that the closest neighbor algorithm is not used in the unit square version of the Traveling Salesman Problem.

Design an algorithm to determine whether a graph is bipartite.

For what values of \(n\) is the \(n\) -cube Eulerian?

Explore the possibility of solving the Traveling Salesman Problem in the "unit box": \([0,1]^{3}\).

Prove that a bipartite graph with an odd number of vertices greater than or equal to 3 has no Hamiltonian circuit.

A particular set of dominoes has 21 tiles: \((1,1),(1,2), \ldots(1,6),(2,2),(2,3), \ldots,(6,6)\). Is it possible to lay all 21 tiles in a line so that each adjacent pair of tile ends matches (that is, each 1 abuts a \(1,\) and so on \() ?\)

How many subgraphs are there of a \(K_{n}, n \geq 1 .\) How many of them are spanning graphs?

Prove that any graph with a finite number of vertices can be drawn in three dimensions so that no edges intersect.

Prove that any graph with a finite mimber of vertices can be drawn in three dimensions so that no edges intersect.

(a) Suppose the edges of a \(K_{6}\) are colored either red or blue. Prove that there will be either a "red \(K_{3}^{\prime \prime}\) (a subset of the vertex set with three vertices connected by red edges) or a "blue \(K_{3}{\underline{\phantom{xx}}}^{\pi}\) or both. (b) Suppose six people are selected at random. Prove that either there exists a subset of three of them with the property that any two people in the subset can communicate in a common language, or there exist three people, no two of whom can communicate in a common language,

Let \(d\) be a positive integer, and let \(a_{1}, a_{2}, \ldots a_{d}\) be positive integers greater than or equal to two. The mesh graph \(M\left(a_{1}, a_{2} \ldots \ldots, a_{d}\right)\) has vertices of the form \(x=\left(x_{1}, x_{2}, \ldots, x_{d}\right)\) where \(1 \leq x_{i} \leq a_{i} .\) Two vertices \(x\) and \(y\) are adjacent if and only if \(\sum_{i=1}^{d}\left|x_{i}-y_{i}\right|=1\). In other words, two adjacent vertices must differ in only one coordinate and by a difference of \(1 .\) (a) What is the chromatic mumber of \(M\left(a_{1}+a_{2} \ldots \ldots, a_{d}\right) ?\) (b) For what pairs \(\left(a_{1}, a_{2}\right)\) does \(M\left(a_{1}, a_{2}\right)\) have a Hamiltonian circuit? (c) For what triples \(\left(a_{1}, a_{2}, a_{3}\right)\) does \(M\left(a_{1}, a_{2}, a_{3}\right)\) have a Hamiltonian circuit?