Exam 10: Graphs

In questions fill in the blanks.1113:1156 - $\text { The edge-chromatic number for } K _ { 2,5 } =$$\underline{\quad\quad}$

In questions fill in the blanks.1113:1156 - $\text { The region-chromatic number for } W _ { 9 } =$$\underline{\quad\quad}$

In questions either give an example or prove that there are none. - $\text { A simple graph with } 6 \text { vertices, whose degrees are } 2,2,2,3,4,4 \text {. }$

In questions either give an example or prove that there are none. -A bipartite graph with an odd number of vertices that has a Hamilton circuit.

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

In the group stage of the 2011 women's soccer world cup the USA beat North Korea, Sweden beat Columbia, the USA beat Columbia, Sweden beat North Korea, Sweden beat the USA, and the game between Columbia and North Korea ended in a tie. Model this outcome using a directed segment from A to B if A beat B, and an undirected segment if the game ended in a tie.

Suppose you have a graph G with vertices v1, v2, . . . , v17 Explain how you would use the adjacency matrix A to find (a) The number of paths from v5 to v3 of length 12 . (b) The length of a shortest path from v5 to v3

Many supermarkets use loyalty or discount cards to keep track of who buys which items. How can graphs be used to model this relationship? Should the edges be directed or undirected? Should multiple edges be allowed? Should loops be allowed? Does this graph have any special properties?

Draw the digraph with adjacency matrix $\left( \begin{array} { l l l l } 0 & 0 & 0 & 0 \\0 & 0 & 1 & 0 \\1 & 1 & 0 & 1 \\1 & 1 & 1 & 0\end{array} \right)$

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

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

In questions fill in the blanks.1113:1156 - $\text { The vertex-chromatic number for } C _ { 15 } =$$\underline{\quad\quad}$

In questions either give an example or prove that there are none. -A planar graph with 7 vertices, 9 edges, and 5 regions.

Find the edge chromatic number for each of the graphs -

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

Find the strongly connected components of the graph.

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

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

In questions either give an example or prove that there are none. -A connected simple planar graph with 5 regions and 8 vertices, each of degree 3.

In questions either give an example or prove that there are none. -A graph with 4 vertices that is not planar.