Chapter 11 Simple Graphs356
(d)Explain why all the edges incident to the end ofwmust already be inw.(e)Show that if the end ofwwas not equal to the start ofw, then the degree of
the end would be odd.
Hint:part (d)
(f)Conclude that if every vertex of a finite, connected graph has even degree, then
it has an Euler tour.
Homework Problems
Problem 11.31.
An edge is said toleavea set of vertices if one end of the edge is in the set and the
other end is not.
(a)Ann-node graph is said to bemangledif there is an edge leaving every set of
bn=2cor fewer vertices. Prove the following:
Claim.Every mangled graph is connected.
Ann-node graph is said to betangledif there is an edge leaving every set of
dn=3eor fewer vertices.
(b)Draw a tangled graph that is not connected.(c)Find the error in the bogus proof of the following
False Claim.Every tangled graph is connected.
Bogus proof.The proof is by strong induction on the number of vertices in the
graph. LetP.n/be the proposition that if ann-node graph is tangled, then it is
connected. In the base case,P.1/is true because the graph consisting of a single
node is trivially connected.
For the inductive case, assumen 1 andP.1/;:::;P.n/hold. We must prove
P.nC1/, namely, that if an.nC1/-node graph is tangled, then it is connected.
So letGbe a tangled,.nC1/-node graph. Choosedn=3eof the vertices and letG 1
be the tangled subgraph ofGwith these vertices andG 2 be the tangled subgraph
with the rest of the vertices. Note that sincen 1 , the graphGhas a least two
vertices, and so bothG 1 andG 2 contain at least one vertex. SinceG 1 andG 2 are
tangled, we may assume by strong induction that both are connected. Also, since
Gis tangled, there is an edge leaving the vertices ofG 1 which necessarily connects
to a vertex ofG 2. This means there is a path between any two vertices ofG: a path
within one subgraph if both vertices are in the same subgraph, and a path traversing
the connecting edge if the vertices are in separate subgraphs. Therefore, the entire