Decision definitions

Loop

An edge that starts and finishes at the same vertex

Trail

A walk in which no edge is visited more than once

Isomorphic graph

Graphs which show the same information but may be drawn differently, they contain the same vertices and arcs

Hamiltonian cycle

A cycle that includes every vertex

Path

A walk in which no vertex is visited more than once

Tree

A connected graph with no cycles

Spanning tree

A subgraph which includes all the vertices of the original graph and is also a tree

Connected graph

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

Walk

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

Simple graph

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

Graph

A graph consists of vertices which are connected by arcs

Cycle

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

Subgraph

A graph, each of whose vertices belongs to the original graph and each whose edges belong to the original graph

Planar graph

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

Tour

A walk which visits every vertex and returns to its start vertex