Adding edges to achieve properties

Questions asking for the minimum number of edges to add to make a graph connected, Eulerian, or Hamiltonian.

2 questions · Standard +0.0

7.02b Graph terminology: tree, simple, connected, simply connected7.02g Eulerian graphs: vertex degrees and traversability7.02h Hamiltonian paths: and cycles
Sort by: Default | Easiest first | Hardest first
AQA D1 2009 June Q7
8 marks Moderate -0.3
7
  1. The diagram shows a graph with 16 vertices and 16 edges. \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_204_365_758} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_202_365_1080} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_204_689_758} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_200_689_1082}
    1. On Figure 1 below, add the minimum number of edges to make a connected graph.
    2. On Figure 2 opposite, add the minimum number of edges to make the graph Hamiltonian.
    3. On Figure 3 opposite, add the minimum number of edges to make the graph Eulerian.
  2. A complete graph has \(n\) vertices and is Eulerian.
    1. State the condition that \(n\) must satisfy.
    2. The number of edges in a Hamiltonian cycle for the graph is the same as the number of edges in an Eulerian trail. State the value of \(n\). \section*{Figure 1} \section*{Connected Graph} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{(a)(i)} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_195_200_2014_758}
      \end{figure} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{(a)(i)} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_197_200_2012_1082}
      \end{figure}
      \includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_202_2334_758}
      \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{(a)(i)} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_202_2334_1080}
      \end{figure} \section*{Figure 2} \section*{Hamiltonian Graph} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_218_536_511_753} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_213_212_836_753} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_215_214_836_1073}
      1. (iii) \section*{Eulerian Graph} \begin{figure}[h]
        \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_207_204_1356_758}
        \end{figure} \begin{figure}[h]
        \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_211_206_1354_1078}
        \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_206_209_1681_753} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_200_202_1681_1080}
AQA D1 2007 January Q8
8 marks Standard +0.3
8
  1. The diagram shows a graph \(\mathbf { G }\) with 9 vertices and 9 edges. \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_188_204_411_708} \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_184_204_415_1105} \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_183_204_612_909}
    1. State the minimum number of edges that need to be added to \(\mathbf { G }\) to make a connected graph. Draw an example of such a graph.
    2. State the minimum number of edges that need to be added to \(\mathbf { G }\) to make the graph Hamiltonian. Draw an example of such a graph.
    3. State the minimum number of edges that need to be added to \(\mathbf { G }\) to make the graph Eulerian. Draw an example of such a graph.
  2. A complete graph has \(n\) vertices and is Eulerian.
    1. State the condition that \(n\) must satisfy.
    2. In addition, the number of edges in a Hamiltonian cycle for the graph is the same as the number of edges in an Eulerian trail. State the value of \(n\).