Graph Theory

This is called a graph

Digraph

A directed graph

Simple

• Undirected

• Unweighted

• No arcs

• No loops

Arc

Two edges connect two vertices

Closed Walk

Starts and ends at the same vertex (eg. A-B-A)

Open Walk

Starts and ends at different vertices (eg. A-B-C)

Path

Walk with no repeat edges or vertices

Closed Path

Walk that repeats no edges or vertices except the initial vertex, ends at initial vertex (eg. A-B-C-D-A)

Open Path

Walk with no repeat edges or vertices, must end at a different place to starting (eg. A-B-C)

Length

Amount of edges crossed

Trail

A walk with no repeated edges but vertices can be repeated. Can be open or closed

Connected

When undirected, if two vertices are joined by any combination of edges

Strongly connected

Each vertex is connected there and back

Weakly connected

Directed graph in which, if undirected, graph would be connected, but direction means some points cannot be reached by path from other vertex

Complete Graph

• Simple

• Connected to every other vertex

• No multiple edges

Adjacent Vertices

Vertices directly joined by an edge

Bridge

An edge in a connected graph that, if removed, would make the graph disconnected

Planar

Can be drawn in the 2-d plane without crosses

Euler’s Rule

V + F = E + 2

Subgraph

A selection of vertices and edges of a larger graph

Tree

Connected graph with no cycles

Cycle

Closed path

Bipartite Graph

Can be split into two groups where every edge connects from one group to another, and no edge connects within a group

Complete bipartite graph

When every vertex in one group connects to all of the vertices in the other group

A complete bipartite graph is

not a complete graph

Degree/ Order

If undirected, the number of edges connected to a vertex

Odd vertex

A vertex with an odd degree

Even vertex

A vertex with an even degree

In degree

Connected into a vertice

Out degree

Directed from a vertice

Eulerian Trail

A closed trail with no odd vertices

Semi-eulerian trail

An open trail with exactly two odd-degree vertices

Hamiltonian Path

A closed path that visits every vertex only once and uses no edge more than once

Semi-hamiltonian path

An open path that visits every vertex only once and uses no edge more than once