Scribd
Upload
15 views3 pages

Solhw 10

The document provides solutions to various exercises related to graph theory, specifically focusing on properties of graphs such as Euler paths and degrees of vertices. It includes proofs demonstrating that a connected graph with exactly two vertices of odd degree contains an Euler path, and that the number of vertices with odd degrees in any graph is even. Additionally, it discusses the necessity of having two vertices with the same degree in a simple graph with at least two vertices.

Uploaded by

timeofdeath321
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views3 pages

Solhw 10

The document provides solutions to various exercises related to graph theory, specifically focusing on properties of graphs such as Euler paths and degrees of vertices. It includes proofs demonstrating that a connected graph with exactly two vertices of odd degree contains an Euler path, and that the number of vertices with odd degrees in any graph is even. Additionally, it discusses the necessity of having two vertices with the same degree in a simple graph with at least two vertices.

Uploaded by

timeofdeath321
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

292 CHAPTER 11.

SOLUTIONS TO THE EXERCISES

1, 2, 3, 4, 5, . . .. Now when n = 1, we get f (1) = 0 and we are left to check


that the negative integers are obtained. But 3, 5, 7, 9, 11, . . . are mapped to
−1, −2, −3, −4, . . .. So this function seems to do what we want! So let us
give a proof. We have to show that f (n) is injective. So suppose f (n) = f (m)
for some positive integers n, m. So either f (n) = f (m) is positive, then we
have
n/2 = m/2 ⇒ n = m
or f (n) = f (m) is negative and

−(n − 1)/2 = −(m − 1)/2 ⇒ n = m.

So this shows the function is injective. Now let us proof that it is surjective
(or onto). We need to show that for any arbitrary m which is an integer,
there exists a positive integer n such that f (n) = m. If m > 0, pick n to
be n = 2m (note that n defined like that is indeed a positive integer), and
f (n) = 2m/2 = m. If m = 0, pick n = 1 and f (1) = 0. If m < 0, then pick
n = −2m + 1. We have f (n) = −[(−2m + 1) − 1]/2 = m and because m is
negative, −2m + 1 is indeed a positive integer.

Exercises for Chapter 10


Exercise 86. Prove that if a connected graph G has exactly two vertices
which have odd degree, then it contains an Euler path.

Solution. Suppose that v and w are the vertices of G which have odd degrees,
while all the other vertices have an even degree. Create a new graph G0 ,
formed by G, with one more edge e, which connects v and w. Every vertex
in G0 has even degree, so by the theorem on Euler cycles, there is an Euler
cycle. Say this Euler cycle is

v, e1 , v2 , e2 , . . . , w, e, v

then
v, e1 , v2 , e2 , . . . , w
is an Euler path.

Exercise 87. Draw a complete graph with 5 vertices.


293

Solution.
Exercise 88. Show that in every graph G, the number of vertices of odd
degree is even.
Solution. Let E denote the set of edges, and write the set V of vertices as
V 0 ∪ V 00 where V 0 is the set of nodes with odd degrees, and V 00 is the set of
nodes with even degrees. Suppose that the number of vertices of odd degree
is odd, then X X X
2|E| = deg(v) = +
v∈V v∈V 0 v∈V 00
where the first sum (over V 0 ) is odd and the second sum is even, a contra-
diction.
Exercise 89. Show that in very simple graph (with at least two vertices),
there must be two vertices that have the same degree.
Solution. Suppose there are n nodes. If all degrees are different, they must
be exactly 0, 1, . . . , n − 1, which is impossible: one cannot have one node of
degree 0, yet another one with degree n − 1!
Exercise 90. Decide whether the following graphs contain a Euler path/cycle.
294 CHAPTER 11. SOLUTIONS TO THE EXERCISES

Solution. The first graph (left hand side) contains a Euler path and no Euler
circuit, the middle graph contains a Euler circuit, the third one contains
none!

You might also like