Computer Science
# Graphs

An *Euler path* in a graph is a path such that every edge is traversed exactly once. Consider the following adjacency matrix representation of the graph:

$A = \left(\begin{array}{lcccr} 0 & 2 & 1 & 0 & 0 \\ 2 & 0 & 2 & 0 & 0 \\ 1 & 2 & 0 & 2 & 2 \\ 0 & 0 & 2 & 0 & 2 \\ 0 & 0 & 2 & 2 & 0 \end{array}\right)$

Write pseudocode to check if the graph contains an Euler path.

A *Hamilton path* of a graph is a path that contains all vertices exactly once. If the last vertex in a Hamilton path has the first vertex as a neighbor, then the path can be turned into a Hamilton circuit by joining the last vertex in the path to the first vertex, i.e, a Hamilton path that is also a cycle is a Hamilton circuit.

Does the following graph allow a Hamilton circuit?

In the adjacency matrix representation of the graph below, how many entries evaluate to `True`

?

Which of the following choices is the minimum spanning tree for the following weighted graph?

**A**

**B**

**C**

**D**