Math 116: Final Exam Study Guide Chapter 11

Chapter 11: Graphs

Exercise 1 Determine the following properties of each graph:

Is the graph simple or a multigraph?
Is the graph complete?
Is the graph connected? If not determine the number of components?
Is the graph a tree or forest?
Determine the degrees of the vertices.

Rendered by QuickLaTeX.com

Graph A: Simple, complete, connected, not a tree, there are three vertices of degree 2.
Graph B: Simple, not complete, connected, tree, there are five vertices of degree 1 and a vertex of degree 5.
Graph C: Simple, not complete, not a tree, there are four vertices of degree 2.
Graph D: Simple, not complete, connected, not a tree, there are two vertices of degree 2, two vertices of degree 3 and one vertex of degree 4.
Graph E: Simple, not complete, not connected, there are two components, a forest, there are four vertices of degree 1.
Graph F: Simple, not complete, connected, tree, there are four vertices of degree 1 and one vertex of degree 4.

Exercise 2 Let $G=(V,E)$ be the graph given by:

Rendered by QuickLaTeX.com

Determine if the following walks are a:

trek
trail
path
cycle
circuit

Walk A: $(c,3,a,1,b,2,c,5,e)$
Walk B: $(a,3,c,5,e,10,i,9,h,8,g)$
Walk C: $(c,5,e,6,f,6,e,7,g,8,h,9,i,10,e,5,c)$

Walk A: It is a trek and trail.
Walk B: It is a trek, trail, and path.
Walk C: It is a cycle.

Exercise 3 How many trails and paths does the following graph have?

Rendered by QuickLaTeX.com

Trails: four of length 0, eight of length 1, eight of length 2, ten of length 3, four of length 4.
Paths: four of length 0, eight of length 1, twelve of length 2, four of length 3.

Exercise 4 A graph has 18 edges and 10 vertices. If 3 vertices have degree 6 and the remaining vertices have degree 2 and 3, how many vertices are there degree 2 and 3?

If there are $18$ edges, then the sum of the degrees of the vertices must be $2\cdot 18=36$ . Let $x$ be the number of degree $2$ vertices and $y$ be the number of degree $3$ vertices. Note that there are $10$ vertices, $3$ of which are degree $6$ . Therefore, we have $x+y=10-3$ and we can set $y=7-x$ .

$\begin{align*} 36 &= 3\cdot 6 + 2\cdot x + 3\cdot (7-x) \\ 36 &= 18+2x+21-3x \\ 36 &= 39-x \\ -3 &= -x \\ 3&= x \end{align*}$

Therefore, there are three degree $2$ vertices and four degree $3$ vertices.

Exercise 5 Determine if the following graphs have an Eulerian circuit or Eulerian trail:

Rendered by QuickLaTeX.com

Graph A: Eulerian trail. Exactly two odd degree vertices.
Graph B: Eulerian trail. Exactly two odd degree vertices.
Graph C: Eulerian circuit. All vertices are of even degree.

Exercise 6 Determine how many spanning trees the following graph has:

There are $4^{4-2}=16$ spanning trees by Cayley’s Theorem (11.2.4).

Malachi Alexander

UCSC Graduate Student

Math 116: Final Exam Study Guide Chapter 11