Chapter 11 Simple Graphs342
Problem 11.5. (a)For any vertex,v, in a graph, letN.v/be the set ofneighbors
ofv, namely, the vertices adjacent tov:
N.v/WWDfujhu—viis an edge of the graphg:Supposef is an isomorphism from graphGto graphH. Prove thatf.N.v//D
N.f.v//.
Your proof should follow by simple reasoning using the definitions of isomorphism
and neighbors—no pictures or handwaving.
Hint:Prove by a chain of iff’s that
h 2 N.f.v// iff h 2 f.N.v//for everyh 2 VH. Use the fact thathDf.u/for someu 2 VG.
(b)Conclude that ifGandHare isomorphic graphs, then for eachk 2 N, they
have the same number of degreekvertices.
Problem 11.6.
Let’s say that a graph has “two ends” if it has exactly two vertices of degree 1 and
all its other vertices have degree 2. For example, here is one such graph:
(a)Aline graphis a graph whose vertices can be listed in a sequence with edges
between consecutive vertices only. So the two-ended graph above is also a line
graph of length 4.
Prove that the following theorem is false by drawing a counterexample.
False Theorem.Every two-ended graph is a line graph.
(b)Point out the first erroneous statement in the following bogus proof of the false
theorem and describe the error.
Bogus proof.We use induction. The induction hypothesis is that every two-ended
graph withnedges is a path.
Base case (nD 1 ):The only two-ended graph with a single edge consists of two
vertices joined by an edge: