Euler Circuits and Paths

Front

What is an Euler Circuit?

Back

An Euler Circuit is a path in a graph that visits every edge exactly once and returns to the starting vertex.

Front

What is an Euler Path?

Back

An Euler Path is a path in a graph that visits every edge exactly once but does not necessarily return to the starting vertex.

Front

What is the condition for a graph to have an Euler Circuit?

Back

A graph has an Euler Circuit if all vertices have even degree.

Front

What is the condition for a graph to have an Euler Path?

Back

A graph has an Euler Path if it has exactly 0 or 2 vertices of odd degree.

Front

How can you determine the degree of a vertex in a graph?

Back

The degree of a vertex is the number of edges connected to it.

Front

If a graph has 3 vertices of odd degree, can it have an Euler Path?

Back

No, a graph cannot have an Euler Path if it has more than 2 vertices of odd degree.

Front

What does it mean to trace all edges on a figure without lifting your pencil?

Back

It means to find an Euler Circuit or Path in the graph.

Front

Can a graph with all vertices of even degree have an Euler Path?

Back

Yes, it can have both an Euler Circuit and an Euler Path.

Front

What is the valence (degree) of a vertex?

Back

The valence (degree) of a vertex is the number of edges incident to that vertex.

Front

If a graph has 2 vertices of odd degree, what can be said about its Euler Path?

Back

The graph will have an Euler Path that starts at one of the odd degree vertices and ends at the other.