Mathematics for Computer Science

11.11. Forests & Trees 343

Sure enough, this is a line graph.

Inductive case:We assume that the induction hypothesis holds for somen 1
and prove that it holds fornC 1. LetGnbe any two-ended graph withnedges.
By the induction assumption,Gnis a line graph. Now suppose that we create a
two-ended graphGnC 1 by adding one more edge toGn. This can be done in only
one way: the new edge must join an endpoint ofGnto a new vertex; otherwise,
GnC 1 would not be two-ended.

gn

new edge

↑

Clearly,GnC 1 is also a line graph. Therefore, the induction hypothesis holds for
all graphs withnC 1 edges, which completes the proof by induction.



Exam Problems

Problem 11.7.
There are four isomorphisms between these two graphs. List them.

1

2

6

3 4

5

a

b

f

c d

e

Problems for Section 11.5

Class Problems

Problem 11.8.
A certain Institute of Technology has a lot of student clubs; these are loosely over-