| Decision 1 Definitions
A list of D1 definitions required for the Edexcel exam
Connected Graph - all pairs of vertices are connected by a path.
Tree - connected graph with no cycles.
Spanning Tree - of a graph G is a subgraph which includes all the verticles of G and is also a tree.
Minimum Spanning Tree (MST) - a spanning tree with the total length of the arcs being as small as possible.
Graph - consists of points connected by lines.
Valency/Degree - of a vertex is the number of edges incident to it.
Subgraph - of G is a graph each of whose vertices and edges belong to G.
Network - a graph which has a number (weight) associated with each edge.
Path - a finite sequence of edges such that the end vertex of one edge is the start vertex of the next, with no vertex appearing more than once.
Cycle - a closed path, i.e. the end vertex of the last edge is the start vertex of the first edge.
Matching - pairing of some or all of the elements in one set with elements of a second set.
Bipartite Graph - consists of 2 sets of vertices X and Y. The edges only join vertices is X to vertices in Y and not vertices within a set. | 
