Decision 1 - Graph Theory

Definitions in graph theory.

A walk

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

A path

A walk in which no vertex is visited more than once

A trail

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

A cycle

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

A Hamiltonian Cycle

A cycle that includes every vertex.

Eulerian Circuit

A trail which traverses every arc and starts and ends at the same vertex.

A Loop

An edge that starts and finishes at the same vertex.

A simple graph

A graph in which there are no loops and there is at most one edge connecting any pair of vertices.

A tree

A connected graph with no cycles

A spanning tree

A subgraph which includes all the vertices and is also a tree.

A completed graph

A graph in which every vertex is directly connected by a single edge to each of the other vertices

Isomorphic graphs

Graphs which show the same information but may be drawn differently

A planar graph

A graph that can be drawn in a plane such that no two edges meet except at a vertex.

Euler’s handshaking lemma

In any undirected graph, the sum of the degrees of the verticies is equal to 2 x the number of edges. As a consequence, the number of odd nodes must be even.