Decision 1: Key Words

Question 1

Define degree or valency

Answer 1

The degree or valency of a vertex is the number of edges incident to it

Question 2

Define path

Answer 2

A finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once

Question 3

Define cycle

Answer 3

A closed path, the end vertex of the last edge is the start vertex of the first edge

Question 4

Define tree

Answer 4

A connected graph with no cycles

Question 5

Define minimum spanning tree

Answer 5

A spanning tree such that the total length of its arcs is as small as possible

Question 6

Define bipartite graph

Answer 6

A bipartite graph consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y

Question 7

Define matching

Answer 7

The pairing of some or all of the elements of one set, X, with elements of a second set, Y.