Mathematics for Computer Science

11.11. References 463

Problem 11.50.
In the cycleC2nof length2n, we’ll call two verticesoppositeif they are on opposite
sides of the cycle, that is that are distancenapart inCn. LetGbe the graph formed
fromC2nby adding an edge, which we’ll call acrossing edge, between each pair
of opposite vertices. SoGhasncrossing edges.

(a)Give a simple description of the shortest path between any two vertices ofG.

Hint:Argue that a shortest path between two vertices inGuses at most one crossing
edge.

(b)What is thediameterofG, that is, the largest distance between two vertices?

(c)Prove that the graph is not 4-connected.

(d)Prove that the graph is 3-connected.

Exam Problems

Problem 11.51.
We apply the following operation to asimple graphG: pick two verticesu¤v
such that either

1. there is an edge ofGbetweenuandv, and there is also a path fromutov
   which doesnotinclude this edge; in this case, delete the edgefu;vg.


2. there is no path fromutov; in this case, add the edgefu;vg.
   Keep repeating these operations until it is no longer possible to find two vertices
   u¤vto which an operation applies.
   Assume the vertices ofGare the integers1;2;:::;nfor somen  2. This
   procedure can be modelled as a state machine whose states are all possible simple
   graphs with vertices1;2;:::;n. Gis the start state, and the final states are the
   graphs on which no operation is possible.

(a)LetGbe the graph with verticesf1;2;3;4gand edges

ff1;2g;f3;4gg

How many possible final states are reachable from start stateG? 1in

(b)On the line next to each of the derived state variables below, indicate the
strongestproperty from the list below that the variable is guaranteed to satisfy,
no matter what the starting graphGis. The properties are:

constant increasing decreasing

nonincreasing nondecreasing none of these