Euler paths

Questions 1 to 5 of 7

1. 1. A connected undirected graph has exactly two vertices of odd degree. What does the lesson say about a walk that uses every edge exactly once?

   It is an Euler cycle, and it can start at either odd vertexIt is an Euler path that must start at one odd vertex and end at the otherNo such walk exists, because two odd vertices is too manyIt is an Euler cycle only when the two odd vertices are next to each other
2. 2. In the lesson's table, what does a connected graph give when every vertex has even degree?

   No Euler pathAn Euler path that must start at a vertex of degree 2An Euler cycle, which can start at any vertex that has edgesAn Euler path that must start at one odd vertex
3. 3. True or false: adding the edge 4-0 to the triangle with a tail gives a graph with an Euler cycle.

   False, because vertex 0 still has an odd degreeTrue, because every degree becomes even and the graph stays connected
4. 4. True or false: two separate triangles, where every vertex has degree 2, form a graph with an Euler cycle.

   False, because the graph is not connected, so one walk cannot use both trianglesTrue, because every degree is even
5. 5. Put the steps of the stack method (Hierholzer's algorithm) in the order the lesson gives them.

   Use the arrows to put the steps in order.

   1. 1.Pop the stuck vertex and write it into the route↑↓
   2. 2.Reverse the route to get the walk in its real order↑↓
   3. 3.Go back to the vertex now on top and walk again if it has unused edges↑↓
   4. 4.Walk along unused edges, pushing each new vertex, until the top vertex is stuck↑↓