Walk
finite sequence of edges so end of one vertex is start of next
Path
walk where no vertex is visited more than once
Trail
walk where no edge is visited more than once
Tour
walk where each vertex is visited at least once, and starts and ends at the same vertex
Cycle
start and end vertex are the same, no vertex is visited more than once
Hamiltonian Cycle
tour where vertex each is visited exactly once
Euler's handshaking lemma
sum of degrees of vertices = 2 x number of edges
Eulerian Graph
all vertices in graph are of even degree
Semi-eulerian Graph
has exactly two nodes of odd degree
Tree
connected graph with no cycles
Spanning Tree
a subgraph which includes all vertices and is a tree
Complete graph
every vertex is connected to every other vertex by a single edge e.g. K5
Isomorphic
graphs which are drawn differently but have the same info
Planar graph
a graph that can be drawn in a plane such that no edges meet except at a vertex