Decision- Graphs Key Words

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