91Ó°ÊÓ

Show that a simple graph that has a circuit with an odd number of vertices in it cannot be colored using two colors.

Suppose that a connected bipartite planar simple graph has \(e\) edges and \(v\) vertices. Show that \(e \leq 2 v-4\) if \(v \geq 3\) .

Suppose that \(G=(V, E)\) is a directed graph. A vertex \(w \in V\) is reachable from a vertex \(v \in V\) if there is a directed path from \(v\) to \(w .\) The vertices \(v\) and \(w\) are mutually reachable if there are both a directed path from \(v\) to \(w\) and a directed path from \(w\) to \(v\) in \(G .\) Show that if \(G=(V, E)\) is a directed graph and \(u, v, v,\) and \(w\) are vertices in \(V\) for which \(u\) and \(v\) are mutually reachable and \(v\) and \(w\) are mutually reachable, then \(u\) and \(w\) are mutually reachable.

Show that a directed multigraph having no isolated vertices has an Euler path but not an Euler circuit if and only if the graph is weakly connected and the in-degree and out-degree of each vertex are equal for all but two vertices, one that has in-degree one larger than its out- degree and the other that has out-degree one larger than its in-degree.

What do the in-degree and the out-degree of a vertex in a directed graph modeling a round-robin tournament represent?

Schedule the final exams for Math 115, Math 116, Math 185, Math 195, CS 101, CS 102, CS 273, and CS 473, using the fewest number of different time slots, if there are no students taking both Math 115 and CS 473, both Math 116 and CS 473, both Math 195 and CS 101, both Math 195 and CS 102, both Math 115 and Math 116, both Math 115 and Math 185, and both Math 185 and Math 195, but there are students in every other pair of courses.

Is a shortest path between two vertices in a weighted graph unique if the weights of edges are distinct?

How many different channels are needed for six stations located at the distances shown in the table, if two stations cannot use the same channel when they are within 150 miles of each other? $$\begin{array}{|c|c|c|c|c|c|}\hline & {1} & {2} & {3} & {4} & {5} & {6} \\\ \hline 1 & {-} & {85} & {175} & {200} & {50} & {100} \\ \hline 2 & {85} & {-} & {125} & {175} & {100} & {160} \\ \hline 4 & {200} & {175} & {100} & {-} & {210} & {220} \\ \hline 5 & {50} & {100} & {200} & {210} & {-} & {100} \\\ \hline 6 & {100} & {160} & {250} & {220} & {100} & {-} \\ \hline\end{array}$$

Which of these nonplanar graphs have the property that the removal of any vertex and all edges incident with that vertex produces a planar graph? \(\begin{array}{llll}{\text { a) } K_{5}} & {\text { b) } K_{6}} & {\text { c) } K_{3,3}} & {\text { d) } K_{3,4}}\end{array}\)

Construct an influence graph for the board members of a company if the President can influence the Director of Research and Development, the Director of Marketing, and the Director of Operations; the Director of Research and Development can influence the Director of Operations; the Director of Marketing can influence the Director of Operations; and no one can influence, or be influenced by, the Chief Financial Officer.