Exam 10: Graphs

Determine whether this graph is planar.

During the construction of a home there are certain tasks that have to be completed before another one can commence, e.g., the roof has to be installed before the work on electrical wiring or plumbing can begin. How can a graph be used to model the different tasks during the construction? Should the edges be directed or undirected? Looking at the graph model, how can we find tasks that can be done at any time and how can we find tasks that do not have to be completed before other tasks can begin?

In questions either give an example or prove that there are none. -A planar graph with 8 vertices, 12 edges, and 6 regions.

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 circuit. }$$\underline{\quad\quad}$

In questions fill in the blanks.1113:1156 - $\text { The length of the longest simple circuit in } W _ { 10 } \text { is }$ .

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 fill in the blanks.1113:1156 -If $G$ is a planar connected graph with 20 vertices, each of degree 3 , then $G$ has $\underline{\quad\quad}$ regions.

Are these two graphs isomorphic?

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

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

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

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

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

How many different channels are needed for six television stations (A, B, C, D, E, F) whose distances (in miles) from each other are shown in the following table? Assume that two stations cannot use the same channel when they are within 150 miles of each other? A B C D E F A - 85 175 100 50 100 B 85 - 125 175 100 130 C 175 125 - 100 200 250 D 100 175 100 - 210 220 E 50 100 200 210 - 100 F 100 130 250 220 100 -

In questions fill in the blanks.1113:1156 - $\text { The Euler formula for planar connected graphs states that }$$\underline{\quad\quad}$

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

In questions fill in the blanks.1113:1156 -The adjacency matrix for $K _ { m , n }$ has $\underline{\quad\quad}$ columns.

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

Draw a cubic graph with 7 vertices, or else prove that there are none.