Euler paths

Questions 1 to 5 of 7

1. 1. A connected undirected graph has an Euler cycle. Which statement must be true of every vertex?

   It has exactly two edgesIt has an odd degreeIt has no self-loopIt has an even degree
2. 2. True or false: a connected undirected graph with exactly two odd-degree vertices has an Euler path, and that path must start at one of those two vertices.

   False, because the route must start at an even vertex and end at an odd vertexTrue, because the route starts at one odd vertex and ends at the other
3. 3. Put these steps of Hierholzer's algorithm in the order the method runs them.

   Use the arrows to put the steps in order.

   1. 1.Pop the stuck vertex into the route list↑↓
   2. 2.Reverse the route list to get the Euler path↑↓
   3. 3.Walk forward from the top vertex along unused edges until stuck↑↓
   4. 4.Push the start vertex onto the stack↑↓
4. 4. In the tickets example, JFK has out-degree 2 and in-degree 1. Where must the directed route start?

   Any airport that has a ticketJFK, because its balance is +1ATL, because it has balance 0SFO, because its balance is -1
5. 5. True or false: two separate triangles have an Euler cycle, because every vertex has an even degree.

   False, because the graph is not connected, so one walk cannot cover both trianglesTrue, because every vertex has an even degree, so the degree rule is met