A Level Further Maths - Discrete - Graphs 1

Vertex

A point on a graph.

Edge

A line or curve with a vertex on each end.

Walk

A sequence of linked vertices.

Trail

A walk that doesn’t repeat any edges.

Path

A walk that doesn’t repeat any edges or vertices.

Cycle

A path that starts and ends at the same vertex.

Hamiltonian Cycle

A cycle that visits every vertex.

Closed Path/Trail/Walk

A path/trail/walk that starts and ends at the same vertex.

Open Path/Trail/Walk

A path/trail/walk that doesn’t start and end at the same vertex.

Connected Graph

A graph where you, starting from one vertex, can get to all other vertices (whether directly or indirectly).

Multiple Edge

A case where there is more than one edge between any two vertices.

Loop

An edge that has the same start and end vertex.

Simple Graph

A graph with no multiple edges and no loops.

Tree

A simple graph that has no cycles.

Subgraph

Any graph that can be formed from the vertices and edges of the original graph.

Subdivision

This is formed when you delete any edge, place a new vertex in between the vertices of the deleted edge, then connect the new vertex back to the original two vertices.

Complete Graph

A simple graph that has every vertex directly connected to every other vertex.

Complement of a Graph

A combination of the edges that need to be added to the original graph to make it a complete graph.

Bipartite Graph

A graph that links two independent groups of vertices. (The vertices in a group are not directly linked to each other.)

Complete Bipartite Graph

A graph, K_{m, n} that links every vertex in group ‘m’ to every vertex in group ‘n’.

Adjacency Matrix

A graph represented in a table form.

Degree of a Vertex

The sum of the number of edges going into a vertex.

Relationship between the Sum of the Degree of Vertices and Edges

Sum of the Degree of Vertices = Edges x 2

K_n

A complete graph with n vertices.

A complete graph has ________ edges.

(1/2)n x (n - 1)