Exam 10: Graphs

In questions either give an example or prove that there are none. -A simple digraph with indegrees 1, 1, 1 and outdegrees 1, 1, 1.

Determine whether the graph is strongly connected, and if not, whether it is weakly connected.

In questions fill in the blanks.1113:1156 - $\text { If a regular graph } G \text { has } 10 \text { vertices and } 45 \text { edges, then each vertex of } G \text { has degree }$$\underline{\quad\quad}$

In questions either give an example or prove that there are none. -A simple graph with degrees 1, 1, 2, 4.

In questions fill in the blanks.1113:1156 - $K _ { n }$ has $\underline{\quad\quad}$ edges and $\underline{\quad\quad}$ vertices.

The picture at the right shows the floor plan of

In questions fill in the blanks.1113:1156 - $Q _ { n }$ has $\underline{\quad\quad}$ edges and $\underline{\quad\quad}$ vertices.

for each graph give an ordered pair description (vertex set and edge set) and an adjacency matrix, and draw a picture of the graph. - $Q _ { 3 }$

In questions fill in the blanks.1113:1156 - $\text { The largest value of } n \text { for which } K _ { n } \text { is planar is }$$\underline{\quad\quad}$

In questions fill in the blanks.1113:1156 - $\text { List all positive integers } n \text { such that } K _ { n } \text { has a Hamilton circuit. }$$\underline{\quad\quad}$

In questions either give an example or prove that there are none. -A graph with 6 vertices that has an Euler circuit but no Hamilton circuit.

Give a recurrence relation for $e _ { n } = \text { the number of edges of the graph } W _ { n }$

In questions either give an example or prove that there are none. -A simple graph with 8 vertices, whose degrees are 0, 1, 2, 3, 4, 5, 6, 7.

Determine whether this graph is planar.

Solve the traveling salesman problem for the graph at the right by finding the total weight of all Hamilton circuits and determining a circuit with minimum total weight.

Consider the graph at the right. (a) Does it have an Euler circuit? (b) Does it have an Euler path? (c) Does it have a Hamilton circuit? (d) Does it have a Hamilton path?

In questions either give an example or prove that there are none. -A graph with a Hamilton circuit but no Hamilton path.

Find the strongly connected components of the graph. For each of the graphs in $56 - 58$ find $\kappa ( G ) , \lambda ( G )$ , and $\min _ { \nu \in V } \operatorname { deg } ( \nu )$ , and determine which of the two inequalities in $\kappa ( G ) \leq \lambda ( G ) \leq \min _ { \nu \in V } \operatorname { deg } ( \nu )$ are strict.