Graph Theory

Nodes

Nodes

Vertices or Vertex Set

Degree/ Order/ Valency

Number of edges coming off a vertice

Walk

A route through a graph along edges from one vertex to the next

Path

A walk where no vertex is visited more than once

Trail

A walk where no edge is visited more than once

Cycle

A walk which the end vertex is the same as the start vertex where no other vertex is visited more than once

Hamiltonian Cycle

A cycle that includes every vertex

Tree

A connected graph with no cycles

Spanning Tree

Includes all vertices and is a tree

Complete Graph

Every vertex is directly connected by a single edge to each of the other vertices

Isomorphic Graph

Show the same information but may be drawn differently

Planar Graph

One that can be drawn in a plane such that no 2 edges meet except at a vertex

Eulerian Graph

Covers every edge exactly once can start and end at any vertex. The degree of each vertice is even

Semi-Eulerian Graphs

Same as Eulerian but ends on a different vertex. It always has two odd degrees