MATH 239 Graph Theory Definitions

Complete Graph

A graph where every vertex is adjacent with every other vertex

k-regular graph

A graph where every vertex has degree k

Subgraph

A graph H is a subgraph of G if E(H) ⊆ E(G) and V(H) ⊆ V(G)

Spanning graph

We say a subgraph H of G is spanning if V(H) = V(G)

Eulerian Trail

A walk that traverses each edge in the graph exactly once

Eulerian Circuit

A cycle that traverses each edge in the graph exactly once

Bridge

An edge e in E(G) such that G - e has more components than G

Tree

A connected graph with no cycles

Forest

A graph with no cycles (each component is a tree)

Planar

A graph is planar if it can be drawn such that:

1. No 2 vertices coincide

2. The edges intersect only at vertices

Boundary

The boundary of face F is the subgraph that contains the edges + vertices incident with F

Boundary Walk

The boundary walk of F is a closed walk obtained by traversing the boundary

Degree

The minimal length of the boundary walk

Length of boundary walk = # of edges in boundary + # of bridges in boundary

X-colouring

A function f : V → X such that whenever uv in E then f(u) ≠ f(v)

k-colouring

An X-colouring where |X| = k

To contract an edge

We contract an edge e = uv by replacing it with a vertex

(replace u,v with new vertex z)

Matching

A set of edges such that no 2 edges in the set are incident with a common vertex

M-saturated

A vertex is M-saturated for matching M if its incident with an edge in M

Perfect Matching

A matching M is perfect if all vertices are M-saturated

Cover

A set C where every edge in G has one end in C

(G-C has no edges)