Discrete Mathematical Structures by Pearson

Author: Uma Shanker Gupta and ISBN: 978-93-325-2139-1

A-78 Solution Manual

A possible graph is

v

1

v

2

v

4

v

3

21. The given graph is partite. The two sets of vertices are

V

1

= {v

1

, v

2

} and V

2

= {v

3

, v

4

, v

5

}

22. The graphs in figs (a) and (b) are both bipartite.

(a) V

1

= {v

1

, v

3

, v

5

} and V

2

= {v

2

, v

4

, v

6

}

(b) V

1

= {A, B, C} and V

2

= {D, E, F, G}

23. (a) Each vertex is of even degree, and hence, the graph is an Eulerian graph.

The Eulerian circuit exists, i.e.,

a → b → c → a

which covers each edge only once

(b) Each vertex is of even degree, and hence, the graph is an Eulerian graph.

The Eulerian circuit exists, i.e.,

a → b → c