MATH220 exam Flashcards
What are adjacent edges?
edges that are incident with a common vertex
define a simple graph
a graph that does not have more than one edge between 2 vertices and does not have an edge that begins and ends at the same vertex
what is a cut vertex?
a vertex that if it is removed it creates a disconnection in the graph
What is the handshaking lemma?
The handshaking lemma states that for any graph G=(V, E), the sum of degrees of the vertices is twice the number of edges:
d(v) = 2|E|
Define an Euler tour
A closed walk that traverses each edge of a graph exactly once.
Define an Eulerian graph
A connected graph is Eulerian if it has an Euler tour.
What is a regular graph?
A graph where each vertex has the exact same number of neighbours, every vertex has the same degree.
What is an Euler trail?
a trail in a finite graph that visits every edge exactly once (allowing for the revisiting of vertices)
What is a Hamiltonian graph?
A graph is hamiltonian if there exists a closed walk in the connected graph that visits every vertex in the graph exactly once (except the starting vertex) without repeating any edges.
How can you tell if a graph has an Euler tour?
A graph has an Euler circuit if and only if the degree of every vertex is even.
How can you tell if a graph has an Euler path?
A graph has an Euler path if and only if there are at most two vertices with odd degree.
