Moderate -0.8 This is a straightforward application of the handshaking lemma (sum of degrees = 2×edges) requiring basic arithmetic, followed by recall of Eulerian definitions and a simple logical argument about connectivity. All parts are standard D1 textbook exercises with no novel problem-solving required.
A graph has six vertices; two are of order 3 and the rest are of order 4. Calculate the number of arcs in the graph, showing your working.
Is the graph Eulerian, semi-Eulerian or neither? Give a reason to support your answer.
A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself.
A connected graph is one in which every vertex is connected, directly or indirectly, to every other vertex.
Explain why a simple graph with six vertices, two of order 3 and the rest of order 4, must also be a connected graph.
2 (i) A graph has six vertices; two are of order 3 and the rest are of order 4. Calculate the number of arcs in the graph, showing your working.\\
(ii) Is the graph Eulerian, semi-Eulerian or neither? Give a reason to support your answer.
A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself.
A connected graph is one in which every vertex is connected, directly or indirectly, to every other vertex.\\
(iii) Explain why a simple graph with six vertices, two of order 3 and the rest of order 4, must also be a connected graph.
\hfill \mbox{\textit{OCR D1 2005 Q2 [5]}}