Decision Maths Definitions

What is a graph?

Consists of a set of vertices or nodes.

These vertices can be connected by edges or arcs.

What is the degree/order of a vertex?

The number of edges coming out of it. If the degree of a vertex is even we call it an even vertex. If the degree of a vertex is odd we call it an odd vertex.

What are Isomorphic graphs?

Two graphs are isomorphic if there is a one-to-one correspondence between their vertices which preserves adjacency. (The same graph, possibly laid out and/or labelled differently.)

What is a subgraph?

A graph whose edges and vertices are contained within the main graph.

What is a walk?

A sequence of connecting edges in a given graph.

What is a trail?

A walk in which no edge is listed more than once.

What is a path?

A walk in which no vertex is visited more than once

What is a cycle?

A path that finishes where it started

What is a connected graph?

A graph where there is a path to all of its vertices

What is a simple graph?

A graph where there are no loops or repeated edges

What is a tree?

A connected graph with no cycles