DA1-DA3 Graph language, Eulerian graphs and Euler's formula Quiz: AQA Further Maths, Unit 5

The 20 questions

1. What condition must every vertex satisfy for a connected graph to be Eulerian?

   • Even degree
   • Prime degree
   • Odd degree
   • Degree of two

2. How many odd degree vertices must a connected graph have to be semi-Eulerian?

   • Any odd number
   • Exactly four
   • Exactly zero
   • Exactly two

3. What property defines a Hamiltonian cycle in a graph?

   • Uses every edge
   • Repeats all vertices
   • Contains no cycles
   • Visits every vertex

4. Which statement is Euler's formula for a connected planar graph with v vertices, e edges and f faces (including the outer face)?

   • v - e + f = 2
   • v + e - f = 2
   • v - e + f = 1
   • e - v + f = 2

5. A connected planar graph has 6 vertices and 9 edges. How many faces does it have, including the outer face?

   • 3
   • 5
   • 4
   • 6

6. The vertices of a simple graph have degrees 3, 3, 2, 2 and 4. How many edges does the graph have?

   • 6
   • 14
   • 7
   • 5

7. A connected graph has vertex degrees 2, 4, 4, 3 and 5. What type of graph is it?

   • Non-connected
   • Eulerian
   • Hamiltonian
   • Semi-Eulerian

8. A complete graph on five vertices, in which every vertex has degree 4, has how many edges?

   • 8
   • 10
   • 5
   • 20

9. The complete graph K4 is drawn in the plane with no crossings. How many faces does this plane drawing have?

   • 2
   • 6
   • 3
   • 4

10. A connected planar graph has 10 edges and 6 faces. How many vertices does it have?

    • 4
    • 18
    • 8
    • 6

11. A connected graph has vertex degrees 2, 2, 4, 4 and 4. What type of graph is it?

    • Non-Eulerian
    • Eulerian
    • Complete
    • Semi-Eulerian

12. What graph operation inserts a degree 2 vertex into an existing edge?

    • Deletion
    • Subdivision
    • Union
    • Contraction

13. In graph theory, what is an edge that connects a vertex to itself called?

    • Multiple edge
    • Arc
    • Loop
    • Bridge

14. What type of walk in a graph has no repeated vertices?

    • Path
    • Trail
    • Cycle
    • Circuit

15. A vertex of a graph has one loop and two other edges. What is the degree of the vertex?

    • 2
    • 3
    • 1
    • 4

16. The complete graph K3 is best described as which of the following?

    • Neither
    • Eulerian only
    • Eulerian and Hamiltonian
    • Hamiltonian only

17. A connected planar graph has 9 vertices, all of degree 4. How many faces does it have, including the outer face?

    • 10
    • 11
    • 12
    • 9

18. How many trails are needed to cover all edges of a connected graph with four odd vertices?

    • Two
    • Four
    • Three
    • One

19. Is a connected Eulerian graph guaranteed to contain a Hamiltonian cycle?

    • Yes
    • No
    • Only if complete
    • Only if planar

20. A connected planar graph has 7 vertices and 5 faces. How many edges does it have?

    • 9
    • 14
    • 12
    • 10

Related quizzes

• Planarity, complete and bipartite graphs Quiz · DA4-DA5 · 20 questions
• Trees and isomorphism of graphs Quiz · DA6-DA7 · 20 questions
• Network language, spanning trees and route inspection Quiz · DB1-DB3 · 20 questions
• Travelling salesperson bounds and refining network models Quiz · DB4-DB5 · 20 questions
• Flows, cuts and the maximum flow-minimum cut theorem Quiz · DC1-DC3 · 20 questions
• Supersources, augmenting flows and capacities Quiz · DC4-DC7 · 20 questions
• Formulating and solving linear programmes graphically Quiz · DD1-DD2 · 20 questions
• The Simplex algorithm Quiz · DD3-DD4 · 20 questions
• Activity networks and critical paths Quiz · DE1-DE3 · 20 questions
• Refining models, Gantt charts and resource levelling Quiz · DE4-DE6 · 20 questions