Chapter 10: Q21RE (page 738)
State the four-color theorem. Are there graphs that cannot be colored with four colors?
Over 22 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
Show that \(g\left( 6 \right) = 2\) by first using exercises \(42\) and \(43\) as well as lemma \(1\) in section \(5.2\) to show that \(g\left( 6 \right) \le 2\) and then find a simple hexagon for which two guards are needed.
Devise an algorithm for finding the second shortest path between two vertices in a simple connected weighted graph.
Suppose that to generate a random simple graph with n vertices we first choose a real number p with\({\bf{0}} \le {\bf{p}} \le {\bf{1}}\). For each of the\({\bf{C}}\left( {{\bf{n,2}}} \right)\)pairs of distinct vertices we generate a random number x between 0 and 1.
If\({\bf{0}} \le {\bf{x}} \le {\bf{p}}\), we connect these two vertices with an edge; otherwise these vertices are not connected.```
a) What is the probability that a graph with m edges where\({\bf{0}} \le {\bf{m}} \le {\bf{C}}\left( {{\bf{n,2}}} \right)\)is generated?
b) What is the expected number of edges in a randomly generated graph with n vertices if each edge is included with probability p?
c) Show that if\({\bf{p = }}\frac{{\bf{1}}}{{\bf{2}}}\)then every simple graph with n vertices is equally likely to be generated.
A property retained whenever additional edges are added to a simple graph (without adding vertices) is called monotone increasing, and a property that is retained whenever edges are removed from a simple graph (without removing vertices) is called monotone decreasing.
What are some applications where it is necessary to find the length of a longest simple path between two vertices in a weighted graph?
Find the edge chromatic number of each of the graphs in
Exercises \(5 - 11\) .
What do you think about this solution?
We value your feedback to improve our textbook solutions.
