Graph Theory Flashcards
(24 cards)
Trail
Walk with no repeated edges
Walk
The sequence of vertices and edges that helps travel from a vertex to any other vertex on a graph
Path
A walk with no repeated vertices except the initial one
Terminal Vertices
The endpoint of a walk
Closed walk
When initial vertex and terminal vertex and the same
Circuit
A closed trail
Cycle
A closed path
Circuitless graph
A graph with no circuits
Length of walk
total # of edges that you go over
Circuitless Thereom
iff there are no loops and there is at most 1 path between any 2 verticies
Bipartitied
simple graph G iff it does not include an odd-length cycle
Connected verticies
If there is a walk between them
connect graph
If a vertices are connect vertices
cut vertex
If the removed vertex causes a connect graph to become disconnected
cut edge
If the removed edge causes a connect graph to become disconnected
Euler walk
walk that uses each edge exactly once
Euler graph
graph has Euler circuit
Euler walk theorem
It has exactly 2 vertices of odd degree
Euler circuit theorem
iff Every vertex has even degree
Hamilton path
A path that uses every vertex in graph exactly once
Hamilton cycle
A cycle that uses every vertex in graph exactly once
Hamilton graph
a graph containing a Hamilton cycle
Hamilton cycle theorem (degree)
simple graph G with n >= 3 vertices such that the degree of each vertex is at least n/2 then G in Hamilton cycle
Hamilton cycle theorem (adjacent)
n>=3 and deg(u) + deg(v) >= n for every non-adjacent vertices u & v, then G has Hamilton Graph
