Exam 10: Graphs

In $K _ { 3,3 }$ let a and b be any two adjacent vertices. Find the number of paths between a and b of length 3.

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

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

In questions fill in the blanks.1113:1156 - $\text { The vertex-chromatic number for } K _ { n } =$

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

A simple graph is regular if every vertex has the same degree. (a) For which positive integers n are the following graphs regular: $C _ { n } , W _ { n } , K _ { n } , Q _ { n } ?$ (b) For which positive integers m and n is $K _ { m , n }$ regular?

The Math Department has 6 committees that meet once a month. How many different meeting times must be used to guarantee that no one is scheduled to be at 2 meetings at the same time, if committees and their members are: C₁={ Allen, Brooks, Marg }, C₂={ Brooks, Jones, Morton }, C₃={ Allen, Marg, Morton } , C₄={ Jones, Marg, Morton }, C₅={ Allen, Brooks }, C₆={ Brooks, Marg, Morton } .

In questions fill in the blanks.1113:1156 - $\text { List all the positive integers } n \text { such that } K _ { 2 , n } \text { is planar. }$$\underline{\quad\quad}$

In $K _ { 5 }$ find the number of paths of length 2 between every pair of vertices.

Use Dijkstra's Algorithm to find the shortest path length between the vertices a and z in this weighted graph.

In questions either give an example or prove that there are none. -A graph with vertex-chromatic number equal to 6.

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

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

Are these two graphs isomorphic?

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

Construct a call graph for five friends Alice, Bob, Charlie, Diane and Evan, if there were three calls from Alice to Bob, two calls from Alice to Diane, five calls from Alice to Evan, one call from Bob to Alice, three calls from Charlie to Alice, one call from Charlie to Evan, one call from Diane to Charlie, and one call from Evan to Diane.

Use Dijkstra's Algorithm to find the shortest path length between the vertices a and z in this weighted graph.

Draw a cubic graph with 8 edges, or else prove that there are none.

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

Give a recurrence relation for $v _ { n } = \text { number of vertices of the graph } Q _ { n } \text {. }$