## D1 - Definitions

The definitions are all based on a pictorial representation of a graph on

*X*×*X*, where X is a finite discrete set.- A
**graph**is a set, or network, of vertices/nodes, each representing a member of a finite discrete set, together with a set of edges/arcs. - A
**subgraph**is a part of a graph. - An
**edge/arc**has a vertex at each end. - A
**weighted graph**has numbers (**weights**) associated with its edges. - A
**loop**is an edge/arc with the same vertex at each end.

- The
**degree/order**of a vertex is the number of arcs/edges incident on it.

- A
**simple graph**is one in which there are no loops and no more than one edge connecting any pair of vertices. - A
**walk**is a sequence of edges in which the end of one edge is the beginning of the next (excluding the final one). - A
**trail**is a walk in which there are no repeated edges. - A
**path**is a trail in which there are no repeated vertices. - A
**cycle/circuit**is a closed path (the end of the final edge is the start of the first edge).

- A
**Hamiltonian cycle**is a cycle which visits every vertex, but only once. - A
**connected graph**is one where there is a path between each vertex pair (doesn’t have to be direct). - A
**tree**is a simple connected graph that has no cycles. - A
**spanning tree**is a subgraph of a graph which includes all the vertices of the graph and is also a tree. - A
**digraph**(directed graph) has at least one edge with an associated direction (arrow arcs). - A
**complete graph**is a simple graph with all pairs of vertices connected by an edge. - An
**incidence/adjacency matrix**represents a graph (see below).

- A
**distance matrix**records the weights on the edges, where a ‘–’ represents no weight.

**Isomorphic graphs**are graphs which have the same attributes but are presented in warped or twisted formats. Once stretched/twisted, these graphs can look exactly the same – without having to change any orders/arcs/nodes. For graphs to be considered isomorphic, the linkage must be the same – meaning the result could be achieved with labelled vertices.- A
**planar graph**has no edges crossing. - A
**bipartite graph**has two distinct sets of vertices – X and Y; edges only join vertices in X to vertices in Y, not vertices within a set. - A
**traversable/Eulerian****graph**can be drawn without taking pen off the paper or repeating edges, starting and ending at the same place. (All nodes are even). - A
**semi-Eulerian graph**is an Eulerian graph but not starting and finishing at the same place. (2 odd nodes, rest even). We call this semi-traversable.

There are always an even (or zero) number of vertices with odd orders in every graph:

- Each arc has two ends and so will contribute two to the total sum of the orders of the whole graph.
- Therefore, the sum of the orders is always even.
- Therefore, vertices with an odd number of orders must exist in pairs.
- Therefore, there is always an even number of odd orders.