Graph Theory

Year 11 Specialists Mathematics

Graph

A mathematical structure and network used to define and visualise relationships between objects

Edge-endpoint Function

A table with a left column of edges and a right column of endpoints

Vertice

Node or point representing a data point or object

Edge

A line representing a relationship between vertices

Multiple Edges

Two or more edges connecting two same vertices

Loop

An edge which connects a vertex to itself

Isolated Vertex

A vertex not connected to any edge or the endpoint of any edge

Adjacency Matrix

A matrix which stores the number of edges between vertices

Simple Graph

A graph without loops or multiple edges

Subgraph

A graph whose vertices and edges are subsets of another graph

Isometric Graphs

Two or more graphs that have a one-to-one correspondence between all of their vertices that preserves the way the vertices are connected by edges

Degree of Vertex

The number of edges that have the vertex as an endpoint, denoted by deg(v).

Size of Graph

Number of edges of a graph, denoted by |E(G)|

Total Degree

Sum of degrees of all the vertices

Handshaking Lemma

Fundamental principle in graph theory, which states that the total degree of any graph is equal to twice the number of edges of the graph

This is because each edge of a graph has two ends, so each edge contributes exactly 2 to the sum of vertex degrees

Walk

A sequence of alternating vertices and edges where edges connect one vertex to the next in a sequence

Bridge

An edge which when removed would increase the number of connected components

Trail

A walk which does not use the same edge more than once

Circuit

A trail which starts and finishes at the same vertex. Also known as a closed trail

Euler Trail

A trail which uses every edge and vertex. For this to be possible, every vertex has to have an even degree or exactly two vertices have to have odd degrees.

Euler Circuit

A circuit that uses every edge and vertex. For this to occur, the degree of eery vertex is even and the graph is connected.

Connected

Walks between all points exists

Disconnected

Walks between all points don’t exist

Fleury's Algorithm

A classic graph theory and algorithm used to identify an Euler circuit
1) If there are two vertices of an odd degree, start from one of them. Otherwise, start from any vertex.
2) Move from the current vertex across an edge to an adjacent vertex. Always choose a non-bridge edge unless there is no alternative.
3) Delete the edge that was traversed
4) Repeat steps 2-3 until the Euler circuit has been identified

Connected Graph

A graph where walks between all vertices exist

Disconnected Graph

A graph where walks between all vertices don’t exist

Hamiltonian Path

A walk that visits every vertex only exactly once

Hamiltonian Cycle

A walk that visits every vertex only exactly once while starting and ending at the same vertex without repeating any edges

Path

A walk with no repeated vertices

Cycle

A circuit that does not repeat any vertices except the vertex that starts and ends the walk

Length

The number of edges, while taking into account its usage, in a walk