Chapter 8

Determine if the simple graphs are isomorphic. When they are, determine an isomorphism \(f.\)

Determine if the simple graphs are isomorphic. When they are, determine an isomorphism \(f.\)

Use the graph in Figure 8.43 to find each. All distinct cycles of length three beginning at \(a\).

Draw the graph with the given adjacency matrix.

Draw the graph with the given adjacency matrix. $$\begin{aligned}&\qquad a\begin{array}{lllll}& b &c & d \end{array} \\\ &\begin{array}{lllll}a \\ b \\ c \\ d \end{array} \quad\left[\begin{array}{llll}0 & 0 & 1 & 1 \\\0 & 0 & 1 & 1 \\\1 & 1 & 0 & 0 \\\1 & 1 & 0 & 0\end{array}\right]\end{aligned}$$

Find the chromatic number of each map or graph. Petersen graph

Draw the graph with the given adjacency matrix.

Draw the graph with the given adjacency matrix. $$\begin{aligned}&\qquad a\begin{array}{lllll}& b &c & d \end{array} \\\ &\begin{array}{lllll}a \\ b \\ c \\ d \end{array} \quad\left[\begin{array}{llll} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{array}\right]\end{aligned}$$

The adjacency matrix of a simple graph has the form $$A=\left[\begin{array}{l|l} A_{1} & 0 \\ \hline 0 & A_{2} \end{array}\right]$$ What can you say about the graph?

A connected, planar graph contains 10 vertices and divides the plane into seven regions. Compute the number of edges in the graph.

Find the chromatic number of each map or graph. Wheel graph \(W_{n}\)

A connected, planar graph contains 24 edges. It divides the plane into 13 regions. How many vertices does the graph have?

Find the chromatic number of each map or graph. 3 -cube \(Q_{3}\)

Show that isomorphism of simple graphs with \(n\) vertices is an equivalence relation.

Find the maximum number of edges in a simple, connected, planar graph with six vertices. With seven vertices.

Characterize graphs with chromatic number 1.

Exactly three vertices with degrees \(1,3,\) and 2.

Find the adjacency matrices of the graphs in Exercises \(1-6.\) Draw the graph with the given list representation.

Let \(G\) be the union of two simple disconnected subgraphs \(H_{1}\) and \(H_{2}\) with chromatic numbers \(m\) and \(n,\) respectively. What can you say about the chromatic number \(c\) of \(G ?\)

Exactly five vertices with degrees \(1,1,1,1,\) and \(4\).

Could there could be a graph that has: Four vertices with degrees \(2,2,2,\) and \(2 ?\)

Find the number of distinct simple paths of length \(n\) in \(K_{5},\) where \(n\) is: $$2$$

Find the number of bonds in each hydrocarbon molecule. (Assume each carbon atom is bonded to four atoms.) A propane molecule \(\mathrm{C}_{3} \mathrm{H}_{8}\)

Find the number of bonds in each hydrocarbon molecule. (Assume each carbon atom is bonded to four atoms.) A butane molecule \(\mathrm{C}_{4} \mathrm{H}_{10}\)

Find the number of bonds in each hydrocarbon molecule. (Assume each carbon atom is bonded to four atoms.) An ethylene molecule \(\mathrm{C}_{2} \mathrm{H}_{4}\)

Find the number of bonds in each hydrocarbon molecule. (Assume each carbon atom is bonded to four atoms.) A cyclobutane molecule \(\mathrm{C}_{4} \mathrm{H}_{8}\)

Find the number of bonds in each hydrocarbon molecule. (Assume each carbon atom is bonded to four atoms.) $$K_{6}$$

Find the number of bonds in each hydrocarbon molecule. (Assume each carbon atom is bonded to four atoms.) $$K_{7}$$

If a connected \(r\) -regular graph is Eulerian, what can you say about \(r ?\)

Let \(G\) be a simple graph with \(n\) vertices. Let \(k\) denote the maximum degree of any vertex in \(G .\) Prove that the chromatic number of \(G\) is \(\leq k+1.\) (Hint: Apply induction on \(n .\) )

Characterize the adjacency matrix of the complete graph \(K_{n}\).

Find the number of vertices in the bipartite graph \(K_{m, n}\).

Find the number of edges in the bipartite graph \(K_{m, n}\).

Identify the general form of the adjacency matrix for \(K_{m, n}\).

Let \(G\) be a graph with \(n\) vertices and \(e\) edges. Let \(M\) and \(m\) denote the maximum and minimum of the degrees of vertices in \(G,\) respectively. Prove that \(m \leq 2 e / n \leq M\).

A simple graph \(G\) is regular if every vertex has the same degree. If every vertex has degree \(r, G\) is \(r\) -regular with \(r\) the degree of the graph. Draw a regular graph with the given properties. \(r=1\) and two vertices.

A simple graph \(G\) is regular if every vertex has the same degree. If every vertex has degree \(r, G\) is \(r\) -regular with \(r\) the degree of the graph. Draw a regular graph with the given properties. \(r=2\) and three vertices.

Prove that a connected graph with \(n\) vertices has at least \(n-1\) edges. (Hint: Use induction.)

A simple graph \(G\) is regular if every vertex has the same degree. If every vertex has degree \(r, G\) is \(r\) -regular with \(r\) the degree of the graph. Draw a regular graph with the given properties. \(r=2\) and four vertices.

Using the adjacency matrix of a graph, write an algorithm to determine if it is connected.

A simple graph \(G\) is regular if every vertex has the same degree. If every vertex has degree \(r, G\) is \(r\) -regular with \(r\) the degree of the graph. Draw a regular graph with the given properties. \(r=3\) and four vertices.

A simple graph \(G\) is regular if every vertex has the same degree. If every vertex has degree \(r, G\) is \(r\) -regular with \(r\) the degree of the graph. Draw a regular graph with the given properties. \(r=2\) and not complete.

Is the complete graph \(K_{n}\) regular? If so, find its degree.

Under what conditions will the complete graph \(K_{n}\) be Hamiltonian?

How many edges does an \(r\) -regular graph with \(n\) vertices have? (Hint: Use Exercise 35.)

If \(G\) is a connected graph containing a vertex with degree 1, can it be Hamiltonian?

Let \(G\) be an \(r\) -regular graph with \(n\) vertices. Prove that \(n r\) is even. (Hint: Use Exercise 44.)

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,3}$$

Can there be a 1-regular graph with three 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_{3,3}$$