Ore's theorem application

Questions requiring use of Ore's theorem to prove a graph is Hamiltonian by checking degree sum conditions.

2 questions · Standard +0.8

7.02f Bipartite test: colouring argument7.02h Hamiltonian paths: and cycles
Sort by: Default | Easiest first | Hardest first
OCR Further Discrete 2022 June Q4
13 marks Challenging +1.2
4 A connected graph is shown below. \includegraphics[max width=\textwidth, alt={}, center]{50697293-6cdc-475f-981f-71a351b0ff5a-4_442_954_296_246}
  1. Write down a path through exactly 7 of the vertices.
  2. Write down a cycle through exactly 6 of the vertices.
  3. Explain why Ore's theorem cannot be used to decide whether or not this graph is Hamiltonian.
  4. Prove that the graph is not Hamiltonian. The following colouring algorithm can be used to determine whether a connected graph is bipartite or not. The algorithm colours each vertex of a graph in one of two colours, (1) and (2). STEP 1 Choose a vertex and assign it colour (1).
    STEP 2 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour (2) to each vertex that is adjacent to a vertex with colour (1).
    STEP 3 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour (1) to each vertex that is adjacent to a vertex with colour (2).
    STEP 4 Repeat STEP 2 and STEP 3 until all vertices are coloured.
    STEP 5 If there are no adjacent vertices of the same colour then the graph is bipartite, output the word "bipartite".
    Otherwise the graph is not bipartite, output the words "not bipartite".
  5. Use this algorithm, starting at vertex A, to determine whether the graph is bipartite, or not. [2
  6. Explain what Kuratowski's theorem tells you about the graph.
  7. Show that the graph has thickness 2 .
AQA Further Paper 3 Discrete 2019 June Q4
6 marks Standard +0.3
4 The connected planar graph \(P\) has the adjacency matrix
\cline { 2 - 6 } \multicolumn{1}{c|}{}\(A\)\(B\)\(C\)\(D\)\(E\)
\(A\)01101
\(B\)10101
\(C\)11011
\(D\)00101
\(E\)11110
4
  1. Draw \(P\) 4
  2. Using Euler's formula for connected planar graphs, show that \(P\) has exactly 5 faces. 4
  3. Ore's theorem states that a simple graph with \(n\) vertices is Hamiltonian if, for every pair of vertices \(X\) and \(Y\) which are not adjacent, $$\text { degree of } X + \text { degree of } Y \geq n$$ where \(n \geq 3\) Using Ore's theorem, prove that the graph \(P\) is Hamiltonian.
    Fully justify your answer.