DP Math AI · HL · Geometry and Trigonometry · Updated

AHL 3.16—Tree and cycle algorithms, Chinese postman, travelling salesman

Get started
Free preview 2/16
  1. Question 1

    A graph has vertices with degrees: , , , , . What can be concluded about Eulerian trails and circuits?
    No clue? Show me the answer
    Correct answerCorrect!Incorrect
    AAn Eulerian trail exists (starting at , ending at ) but not a circuit

    Step-by-step walkthrough

    Choose a solution method

    Method #1Worked solution

    Step 1: Count odd-degree vertices

    Degrees are . The odd-degree vertices are and .

    Step 2: Apply the Eulerian rule

    A connected graph with exactly two odd-degree vertices has an Eulerian trail but not a circuit.

    Step 3: Determine endpoints

    The trail must start at one odd-degree vertex and end at the other, so it runs from to (or vice versa).

    Step 4: State conclusion

    Since there are exactly two odd vertices, an Eulerian trail exists but no Eulerian circuit.

    Method #2Why the others are wrong

    Step 1: Option A

    An Eulerian circuit requires all vertices to have even degree; here and are odd, so no circuit exists.

    Step 2: Option C

    Exactly two odd vertices guarantees a trail exists, so claiming neither exists is incorrect.

    Step 3: Option D

    has even degree, so a trail cannot both start and end there while covering every edge.

    Step 4: Correct choice

    Only option B correctly identifies the trail and its endpoints.

  2. Question 2

    Which statement correctly distinguishes a trail from a path in an undirected graph?
    No clue? Show me the answer
    Correct answerCorrect!Incorrect
    BA trail cannot repeat edges; a path cannot repeat vertices

    Step-by-step walkthrough

    Choose a solution method

    Method #1Worked solution

    Step 1: Recall definitions

    A trail is a walk with no repeated edges, while a path is a walk with no repeated vertices.

    Step 2: Compare the definitions

    Since repeating a vertex would force at least one edge to be repeated only in specific cases, but the fundamental restriction differs: trails restrict edges, paths restrict vertices.

    Step 3: Match to options

    Option B states trail = no repeated edges, path = no repeated vertices, matching the definitions exactly.

    Step 4: Conclusion

    Therefore option B is correct.

    Method #2Why the others are wrong

    Step 1: Option A

    This reverses the definitions - a trail actually restricts edges, not vertices.

    Step 2: Option C

    Returning to the start describes a circuit or cycle, not the trail/path distinction.

    Step 3: Option D

    Trails and paths are distinct concepts; every path is a trail but not every trail is a path.

    Step 4: Correct choice

    Option B correctly captures the edge-vs-vertex distinction.

Free preview

14 more questions in this topic

Checking your topic access