Mathematics for Computer Science

Chapter 11 Simple Graphs466

000

001

010

011

100

101

110

111

Figure 11.34 H 3.

Problem 11.58.
Thediameterof a connected graph is the largest distance between any two vertices.

(a)What is the largest possible diameter in any connected graph withnvertices?
Describe a graph with this maximum diameter.

(b)What is the smallest possible diameter of ann-vertex tree forn > 2? Describe
ann-vertex tree with this minimum diameter.

Problem 11.59.

(a)Circle all the properties below that are preserved under graph isomorphism.

There is a cycle that includes all the vertices.

Two edges are of equal length.

The graph remains connected if any two edges are removed.

There exists an edge that is an edge of every spanning tree.

The negation of a property that is preserved under isomorphism.

(b)For the following statements aboutfinite trees, circletrueorfalse, andpro-
vide counterexamplesfor those that arefalse.

Any connected subgraph is a tree. true false

Adding an edge between two nonadjacent vertices creates a cycle. true

false

The number of vertices is one less than twice the number of leaves. true

false

The number of vertices is one less than the number of edges.true false