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.

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

Let \(G=(V, E)\) be a connected undirected graph. a) What is the largest possible value for \(|V|\) if \(|E|=19\) and \(\operatorname{deg}(v) \geq 4\) for all \(v \in V\) ? b) Draw a graph to demonstrate each possible case in part (a).

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.

If \(n \geq 3\), how many different Hamilton cycles are there in the wheel graph \(W_{n} ?\)

a) Let \(G=(V, E)\) be a connected bipartite undirected graph with \(V\) partitioned as \(V_{1} \cup V_{2}\). Prove that if \(\left|V_{1}\right| \neq\left|V_{2}\right|\), then \(G\) cannot have a Hamilton cycle. b) Prove that if the graph \(G\) in part (a) has a Hamilton path, then \(\left|V_{1}\right|-\left|V_{2}\right|=\pm 1\). c) Give an example of a connected bipartite undirected graph \(G=(V, E)\), where \(V\) is partitioned as \(V_{1} \cup V_{2}\) and \(\left|V_{1}\right|=\left|V_{2}\right|-1\), but \(G\) has no Hamilton path.

Give an example of a connected graph \(G\) where removing any edge of \(G\) results in a disconnected graph.

Let \(G\) be a cycle on \(n\) vertices. Prove that \(G\) is self-complementary if and only if \(n=5\).

Let \(G=(V, E)\) be an undirected connected loop-free graph. Suppose further that \(G\) is planar and determines 53 regions. If, for some planar embedding of \(G\), each region has at least five edges in its boundary, prove that \(|V| \geq 82\).