Graph Theory Quiz-Euler Path and Circuit

An Euler path in a graph is a path that

• Visits every vertex exactly once

• Visits every edge exactly once

• Visits every vertex and edge exactly once

• Starts and ends at the same vertex

An Euler circuit must

• Start and end at the same vertex

• Visit every vertex exactly once

• Contain no repeated edges or vertices

• Exist only in directed graphs

A connected graph has an Euler circuit if and only if

• All vertices have odd degree

• All vertices have even degree

• It has exactly two odd-degree vertices

• It has no loops

A connected graph has an Euler path but not an Euler circuit if and only if

• All vertices have even degree

• Exactly two vertices have odd degree

• Exactly one vertex has odd degree

• More than two vertices have odd degree

Euler’s Theorem applies to

• Directed graphs only

• Undirected graphs only

• Both directed and undirected graphs

• Trees only

The sum of degrees of all vertices is

• Equal to the number of vertices

• Equal to twice the number of edges

• Equal to the number of edges

• Always odd

The Königsberg bridge problem led to

• Hamilton’s theory

• Euler’s theory

• Dijkstra’s algorithm

• Kruskal’s theorem

A disconnected graph can never have

• An Euler path

• An Euler circuit

• Both A and B

The degree of a vertex is

• Number of vertices adjacent to it

• Number of edges incident on it

• Both A and B

• None

If all vertices have even degree, then

• The graph is Hamiltonian

• The graph is Eulerian

• The graph is complete

• The graph is planar