Eulerian classification

Questions asking to classify a graph as Eulerian, semi-Eulerian, or neither, with justification based on vertex degrees.

5 questions · Moderate -0.4

7.02g Eulerian graphs: vertex degrees and traversability
Sort by: Default | Easiest first | Hardest first
OCR D1 2007 June Q1
9 marks Moderate -0.8
1 Two graphs A and B are shown below. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{dbf782dd-879c-4f0f-b532-246a0db9f130-2_339_585_333_386} \captionsetup{labelformat=empty} \caption{Graph \(A\)}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{dbf782dd-879c-4f0f-b532-246a0db9f130-2_337_579_333_1174} \captionsetup{labelformat=empty} \caption{Graph B}
\end{figure}
  1. Write down an example of a cycle on graph A .
  2. W hy is \(\mathrm { U } - \mathrm { Y } - \mathrm { V } - \mathrm { Z } - \mathrm { Y } - \mathrm { X }\) not a path on graph B ?
  3. How many arcs would there be in a spanning tree for graph A ?
  4. For each graph state whether it is Eulerian, semi-Eulerian or neither.
  5. The graphs show designs to be etched on metal plates. The etching tool is positioned at a starting point and follows a route without repeating any arcs. It may be lifted off and positioned at a new starting point. W hat is the smallest number of times that the etching tool must be positioned, including the initial position, to draw each graph? An arc is drawn connecting Q to U , so that the two graphs become one. The resulting graph is not Eulerian.
  6. Extra arcs are then added to make an Eulerian graph. W hat is the smallest number of extra arcs that need to be added?
OCR Further Discrete AS Specimen Q4
6 marks Moderate -0.3
4 Two graphs are shown below. Each has exactly five vertices with vertex orders 2, 3, 3, 4, 4 . \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{a6800c9f-583b-493a-906c-015df63b842f-3_605_616_360_278} \captionsetup{labelformat=empty} \caption{Graph 1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{a6800c9f-583b-493a-906c-015df63b842f-3_420_501_497_1169} \captionsetup{labelformat=empty} \caption{Graph 2}
\end{figure}
  1. Write down a semi-Eulerian route for graph 1 .
  2. Explain how the vertex orders show that graph 2 is also semi-Eulerian.
  3. By referring to specific vertices, explain how you know that these graphs are not simple.
  4. By referring to specific vertices, explain how you know that these graphs are not isomorphic.
AQA Further Paper 3 Discrete 2020 June Q5
4 marks Moderate -0.5
5 The planar graph \(P\) is shown below. \includegraphics[max width=\textwidth, alt={}, center]{c297a67f-65fd-47e0-a60c-d38fd86c6081-08_410_406_360_817} 5
  1. Determine the number of faces of \(P\).
    5
  2. Akwasi claims that \(P\) is semi-Eulerian as it is connected and it has exactly two vertices with even degree. Comment on the validity of Akwasi's claim. \includegraphics[max width=\textwidth, alt={}, center]{c297a67f-65fd-47e0-a60c-d38fd86c6081-09_2488_1716_219_153}
AQA Further Paper 3 Discrete 2023 June Q8
6 marks Moderate -0.3
8 The graph \(G\) is shown below. \includegraphics[max width=\textwidth, alt={}, center]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-12_301_688_351_676} 8
    1. State, with a reason, whether or not \(G\) is simple. 8
      1. (ii) A student states that \(G\) is Eulerian.
        Explain why the student is correct. 8
    2. The graph \(H\) has 8 vertices with degrees 2, 2, 4, 4, 4, 4, 4 and 4 Comment on whether \(H\) is isomorphic to \(G\) 8
    3. The formula \(v - e + f = 2\), where \(v =\) number of vertices \(e =\) number of edges \(f =\) number of faces
      can be used with graphs which satisfy certain conditions. Prove that \(G\) does not satisfy the conditions for the above formula to apply.
OCR FD1 AS 2017 Specimen Q4
6 marks Moderate -0.3
4 Two graphs are shown below. Each has exactly five vertices with vertex orders 2, 3, 3, 4, 4 . \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{da50ab63-a6f5-4533-ba6d-f9941b71038f-03_602_611_360_280} \captionsetup{labelformat=empty} \caption{Graph 1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{da50ab63-a6f5-4533-ba6d-f9941b71038f-03_420_499_497_1169} \captionsetup{labelformat=empty} \caption{Graph 2}
\end{figure}
  1. Write down a semi-Eulerian route for graph 1.
  2. Explain how the vertex orders show that graph 2 is also semi-Eulerian.
  3. By referring to specific vertices, explain how you know that these graphs are not simple.
  4. By referring to specific vertices, explain how you know that these graphs are not isomorphic.