91Ó°ÊÓ

For each of these problems about a subway system, describe a weighted graph model that can be used to solve the problem. a) What is the least amount of time required to travel between two stops? b) What is the minimum distance that can be traveled to reach a stop from another stop? c) What is the least fare required to travel between two stops if fares between stops are added to give the total fare?

Show that the sum, over the set of people at a party, of the number of people a person has shaken hands with, is even. Assume that no one shakes his or her own hand.

What does the degree of a vertex represent in the acquaintanceship graph, where vertices represent all the people in the world? What does the neighborhood of a vertex in this graph represent? What do isolated and pendant vertices in this graph represent? In one study it was estimated that the average degree of a vertex in this graph is 1000. What does this mean in terms of the model?

Let \(G\) be an undirected graph with a loop at every vertex. Show that the relation \(R\) on the set of vertices of \(G\) such that \(u R v\) if and only if there is an edge associated to \(\\{u, v\\}\) is a symmetric, reflexive relation on \(G .\)

Suppose that a connected planar graph has eight vertices, each of degree three. Into how many regions is the plane divided by a planar representation of this graph?

The intersection graph of a collection of sets \(A_{1}\) , \(A_{2}, \ldots, A_{n}\) is the graph that has a vertex for each of these sets and has an edge connecting the vertices representing two sets if these sets have a nonempty intersection. Construct the intersection graph of these collections of sets. a) \(A_{1}=\\{0,2,4,6,8\\}, A_{2}=\\{0,1,2,3,4\\}\) \(A_{3}=\\{1,3,5,7,9\\}, A_{4}=\\{5,6,7,8,9\\}\) \(A_{5}=\\{0,1,8,9\\}\) b) \(A_{1}=\\{\ldots,-4,-3,-2,-1,0\\}\) \(A_{2}=\\{\ldots,-2,-1,0,1,2, \ldots\\}\) \(A_{3}=\\{\ldots,-6,-4,-2,0,2,4,6, \ldots\\}\) \(A_{4}=\\{\ldots,-5,-3,-1,1,3,5, \ldots\\}\) \(A_{5}=\\{\ldots,-6,-3,0,3,6, \ldots\\}\) c) \(A_{1}=\\{x | x < 0\\}\) \(A_{2}=\\{x |-1 < x < 0\\}\) \(A_{3}=\\{x | 0 < x < 1\\}\) \(A_{4}=\\{x |-1 < x < 1\\}\) \(A_{5}=\\{x | x > -1\\}\) \(A_{6}=\mathbf{R}\)

Suppose that a connected planar graph has six vertices, each of degree four. Into how many regions is the plane divided by a planar representation of this graph?

What does the degree of a vertex represent in an academic collaboration graph? What does the neighborhood of a vertex represent? What do isolated and pendant vertices represent?

Suppose that a connected planar graph has 30 edges. If a planar representation of this graph divides the plane into 20 regions, how many vertices does this graph have?

Draw the acquaintanceship graph that represents that Tom and Patricia, Tom and Hope, Tom and Sandy, Tom and Amy, Tom and Marika, Jeff and Patricia, Jeff and Mary, Patricia and Hope, Amy and Hope, and Amy and Marika know each other, but none of the other pairs of people listed know each other.