91Ó°ÊÓ

Give an example of a connected graph that has (a) Neither an Euler circuit nor a Hamilton cycle. (b) An Euler circuit but no Hamilton cycle. (c) A Hamilton cycle but no Euler circuit. (d) Both a Hamilton cycle and an Euler circuit.

Determine \(|V|\) for the following graphs or multigraphs \(G\). a) \(G\) has nine edges and all vertices have degree 3 . b) \(G\) is regular with 15 edges. c) \(G\) has 10 edges with two vertices of degree 4 and all others of degree 3 .

Show that when any edge is removed from \(K_{5}\), the resulting subgraph is planar. Is this true for the graph \(K_{3,3}\) ?

a) If the edges of \(K_{6}\) are painted either red or blue, prove that there is a red triangle or a blue triangle that is a subgraph. b) Prove that in any group of six people there must be three who are total strangers to one another or three who are mutual friends.

a) How many vertices and how many edges are there in the complete bipartite graphs \(K_{4,7}, K_{7,11}\), and \(K_{m, n}\), where \(m, n, \in \mathbf{Z}^{+} ?\) b) If the graph \(K_{m, 12}\) has 72 edges, what is \(m\) ?

Prove that any subgraph of a bipartite graph is bipartite.

Find all (loop-free) nonisomorphic undirected graphs with four vertices. How many of these graphs are connected?

Let \(V=\\{a, b, c, d, e, f\\}\). Draw three nonisomorphic loop-free undirected graphs \(G_{1}=\left(V, E_{1}\right), G_{2}=\left(V, E_{2}\right)\), and \(G_{3}=\left(V, E_{3}\right)\), where, in all three graphs, we have \(\operatorname{deg}(a)=3\), \(\operatorname{deg}(b)=\operatorname{deg}(c)=2\), and \(\operatorname{deg}(d)=\operatorname{deg}(e)=\operatorname{deg}(f)=1\).

Let \(n \in \mathbf{Z}^{+}\)with \(n \geq 4\). How many subgraphs of \(K_{n}\) are isomorphic to the complete bipartite graph \(K_{1,3}\) ?

a) For \(n \geq 3\), how many different Hamilton cycles are there in the complete graph \(K_{n}\) ? b) How many edge-disjoint Hamilton cycles are there in \(K_{21} ?\) c) Nineteen students in a nursery school play a game each day where they hold hands to form a circle. For how many days can they do this with no student holding hands with the same playmate twice?