91Ó°ÊÓ

Solve the Chinese postman problem for the complete graph \(K_{6}\).

Prove that a multigraph is bipartite if and only if each of its connected components is bipartite.

Prove that \(K_{m, n}\) is isomorphic to \(K_{n, m}\).

Let \(V=\\{1,2, \ldots, 20\\}\) be the set of the first 20 positive integers. Consider the graphs whose vertex set is \(V\) and whose edge sets are defined below. For earth graph, investigate whether the graph (i) is connected (if not connected, determin" the connected components), (ii) is bipartite, (iii) has an Eulerian trail, and (iv) has a Hamilton path. (a) \(\\{a, b\\}\) is an edge if and only if \(a+b\) is even. (b) \(\\{a, b\\}\) is an edge if and only if \(a+b\) is odd. (c) \(\\{a, b\\}\) is an edge if and only if \(a \times b\) is even. (d) \(\\{a, b\\}\) is an edge if and only if \(a \times b\) is odd. (e) \(\\{a, b\\}\) is an edge if and only if \(a \times b\) is a perfect square. (f) \(\\{a, b\\}\) is an edge if and only if \(a-b\) is divisible by 3 .

Find a knight's tour on the boards of the following sizes: (a) \(5-\mathrm{by}-5\) (b) 6 -by-6 (c) 7 -by - 7

\(*\) Prove that there does not exist a knight's tour on a 4 -by-4 board.

Prove that a graph is a tree if and only if it does not contain any cycles, but the insertion of any new edge always creates exactly one cycle.

Grow all the nonisomorphic trees of order \(7 .\)

Let \(\left(d_{1}, d_{2}, \ldots, d_{n}\right)\) be a sequence of integers. (a) Prove that there is a tree of order \(n\) with this degree sequence if and only if \(d_{1}, d_{2}, \ldots, d_{n}\) are positive integers with sum \(d_{1}+d_{2}+\cdots+d_{n}=2(n-1)\). (b) Write an algorithm that, starting with a sequence \(\left(d_{1}, d_{2}, \ldots, d_{n}\right)\) of positive integers, either constructs a tree with this degree sequence or concludes that none is possible.

Prove that the removal of an edge from a tree leaves a forest of two trees.