Decision 1 - Graph Definitions

Graph theory definitions from decision 1 maths edexcel.

Graph

Consists of points (called vertices or nodes) which are connected by lines (edges or arcs)

Subgraph

A graph where each of the vertices belongs to the original graph and each of the edges belongs to the original graph.

Degree, Valency, Order

Number of edges incident to the vertex.

Walk

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

Path

A walk in which no vertex is visited more than once

Trail

A walk in which no edge is visited more than once

Cycle

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

Hamiltonian Cycle

A cycle that includes every vertex

Euler’s Handshaking Lemma

In un-directed graph, sum of degrees of vertices = 2 x number of edges. Number of odd nodes must be even.

Simple Graph

No loops and at most one edge connecting any pair of vertices

Tree

Connected graph with no cycles

Spanning Tree

Sub-graph includes all the vertices of the original graph and is a tree

Isomorphic graphs

Shows the same information but may be drawn differently

Adjacency Matrix

Describes the number of arcs joining the corresponding vertices

Distance Matrix

Entries represents the weight of each arc