91Ó°ÊÓ

How many nonisomorphic graphs of order 1 are there? of order \(2 ?\) of order 3? Explain why the answer to each of the preceding questions is \(\infty\) for general graphs.

Determine each of the 11 nonisomorphic graphs of order 4, and give a planar representation of each.

Does there exist a graph of order 5 whose degree sequence equals \((4,4,4,2,2) ?\) a multigraph?

Use the pigeonhole principle to prove that a graph of order \(n \geq 2\) always has two vertices of the same degree. Does the same conclusion hold for multigraphs?

Draw a connected graph whose degree sequence equals $$ (5,4,3,3,3,3,3,2,2) $$

Prove that, if two vertices of a general graph are joined by a walk, then they are joined by a path.

Let \(G\) be a connected graph of order 6 with degree sequence \((2,2,2,2,2,2)\). (a) Determine all the nonisomorphic induced subgraphs of \(G\). (b) Determine all the nonisomorphic spanning subgraphs of \(G\). (b) Determine all the nonisomorphic subgraphs of order 6 of \(G\).

Let \(G\) be a general graph and let \(G^{\prime}\) be the graph obtained from \(G\) by deleting all loops and all but one copy of each edge with multiplicity greater than 1. Prove that \(G\) is connected if and only if \(G^{\prime}\) is connected. Also prove that \(G\) is planar if and only if \(G^{\prime}\) is planar.

Which complete graphs \(K_{n}\) have closed Eulerian trails? open Eulerian trails?

Determine all nonisomorphic graphs of order at most 6 that have a closed Eulerian trail.