Graph Theory Flashcards
1
Q
Circuit
A
ends at beginning, no repeated edges
2
Q
Cycle
A
ends at beginning, no repeated vertices
3
Q
Complement of a graph G
A
A graph with the same vertices as g, but has an edge between any 2 vertices that G doesn’t
4
Q
Bipartite graph
A
vertices can be divided into 2 sets, such that no vertices in the same set are connected
5
Q
Complete graph
A
All vertices are connected
6
Q
Connected graph
A
Each pair of vertices is joined by a path
7
Q
Simple
A
no loops, no double edges
8
Q
Walk
A
any sequence of edges
9
Q
Trail
A
no repeated edges
10
Q
Path
A
No repeated vertices
11
Q
Eulerian
A
every edge exactly once
12
Q
Hamiltonian
A
every vertex exactly once
13
Q
Planar graph
A
no edges cross in drawing
14
Q
Tree
A
graph that contains no cycles
15
Q
Graph isomorphism
A
2 graphs are exactly the same
