Key Concepts
Vertex Set
List of vertices in a graph.
A sequence of adjacent edges, where the edges are used only once.
Path
Circuit
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.
Problems concerned with routing the delivery of goods or services to a set of destinations.
Routing problem
Edge list
List of edges in a graph.
The number of edges in a path.
length
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.
Problems where a specific set of connections (roads, bridges, edges) must me traveled at least once.
Street-routing problem
A vertex with degree zero.
Isolated vertex
A graph in which a path exists between any two vertices
Connected graph
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
Two vertices sharing the same edge
adjacent vertices
Connected parts of a graph
components
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
An edge that connects a vertex with itself.
loop
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