Key Concepts
A walk is .........
A walk is a sequence of connect vertices.
An Eulerian trail is a ......... with no ......... edges that includes every ....... in a graph.
An Eulerian trail is a walk with no repeated edges that includes every edge in a graph.
A path that starts and ends at the same vertex.
Cycle
A graph with 8 vertices has an Euler Circuit. What can you say about the degree of each vertex.
Each vertex must have an even degree.
What is a Hamiltonian path
a walk with no repeated vertices that includes every vertex in a graph.
A trail is ............
A trail is a walk with no repeated edges.
An Eulerian graph will only exist if all the vertices are .......
Even
A path in a connected graph that passes that starts and ends at the same vertex, and passes through every edge of the graph one and only once.
Euler Circuit
A graph with 9 vertices has an Euler path but no Euler Circuit. The graph mus have
2 vertices of odd degree and 7 vertices of even degree.
What is a Hamiltonian cycle
a walk with no repeated vertices that includes every vertex in a graph and starts and finishes at the same vertex.
A closed trail is ........
A closed trail is a walk with no repeated edges that starts and finishes at the same vertex.
A semi Eulerian trail will only exist if ...............
exactly two vertices of odd degrees.
Will a complete graph of 3 vertices have an Euler Circuit? Yes or No.
Yes
A graph has an Euler path but no Euler circuit. There are 25 vertices in the graph. The graph must have...
2 vertices of odd degree and 23 vertices of even degrees.
An edge that connects a vertex with itself
loop
A path is .......
A path is a walk with no repeated edges and no repeated vertices.
To find the Eulerian trail, you must start at ..........
one of the two odd degree vertex and finish at the other odd degree vertex.
Will a complete graph with 4 vertices have an Euler Circuit? Yes or no?
No
For a graph to have an Euler Path it must have 4 odd vertices. True or False
False
Two or more edges connecting the two vertices
multiple-edges
A cycle is ...........
A cycle is a walk with no repeated edges and no repeated vertices that starts and finishes at the same vertex.
A path in a connected graph that passes through every edge of the graph once and only once.
Euler path
How do you know if a graph has an Euler Circuit?
If all vertices have even degrees.
The process of duplicating edges in a graph to make it have all but even vertices.
Eulerization
Number of edges meeting at the vertex
degree