Homework 9

CS 280 - Spring 2002

Due: Friday, April 26

Assume that the term graph refers to a simple graph unless otherwise indicated.

Part A

  1. The distance between two vertices in a graph is the length of the shortest path between them.  The radius at v for graph is the maximum distance between v and and another vertex.  The radius of a graph is the minimum over all vertices v of the radius at v.  The diameter of a graph is the maximum distance between two distinct vertices.
    1. Find the radius and diameter of K5. 
    2. Find the radius and diameter of K4,7.
    3. Find the radius and diameter of Q4.
    4. Find the radius and diameter of C7.
       
  2. What is the relation between the radius (R) and the diameter (D) of a connected graph?  In other words, the goal is to find constants c1 and c2 such that c1R < D < c2R holds for any connected graph and such that c1 is as large as possible and c2 is as small as possible.  For each of c1 and c2 either (1) choose a value for the constant, give a proof to show that your chosen bound holds, and give an example that achieves your stated bound or (2) show that no such constant exists (by describing graph or a sequence of graphs that contradict any chosen constant).

Part B

  1. How many nonisomorphic subgraphs does Q2 have?  Recall that a graph is a subgraph of itself and that, by definition, a graph must have at least one vertex.
     
  2. Claim: In any finite simple graph with at least two vertices there are always two vertices with the same degree.  Either prove the claim true or give a counterexample.

Part C

  1.  
    1. Can 9 segments be drawn in the plane so that each intersects exactly 3 others?  Prove your answer.
    2. Suppose G has 10 vertices, each of degree 5.  Show that G is not planar.
       
  2. Some friends of yours are working on wireless networks consisting of n mobile devices.  Each user reports on who they can communicate with at noon on a particular day.  Alice reports that her device can communicate directly with only one other device.  Bob reports that his device can communicate directly with 19 other devices.  All the remaining users report that each remaining device can communicate directly with exactly 20 other devices.  Prove that there is a communication path between Alice and Bob.  (Hint: Think of the graph built using a vertex for each device and an edge between two devices if they can communicate directly.  The goal is to show that there is a path between Alice and Bob in this graph.)