Definitions

Question 1

Handshaking Lemma

Answer 1

The sum of the degrees of all the vertices in a graph is equal to twice the number of edges.

Question 2

Bipartite graph

Answer 2

A graph whose vertices can be divided into two sets such that no two vertices in the
same set are adjacent.

Question 3

Circuit

Answer 3

A walk that begins and ends at the same vertex, and has no repeated edges.

Question 4

Complement of a graph G

Answer 4

A graph with the same vertices as G but which has an edge between any two
vertices if and only if G does not.

Question 5

Complete bipartite

graph

Answer 5

A bipartite graph in which every vertex in one set is joined to every vertex in the
other set.

Question 6

Complete graph

Answer 6

A simple graph in which each pair of vertices is joined by an edge.

Question 7

Connected graph

Answer 7

A graph in which each pair of vertices is joined by a path.

Question 8

Cycle

Answer 8

A walk that begins and ends at the same vertex, and has no other repeated vertices.

Question 9

Degree of a vertex

Answer 9

The number of edges joined to the vertex; a loop contributes two edges, one for
each of its end points.

Question 10

Disconnected graph

Answer 10

A graph that has at least one pair of vertices not joined by a path.

Question 11

Eulerian circuit

Answer 11

A circuit that contains every edge of a graph.

Question 12

Eulerian trail

Answer 12

A trail that contains every edge of a graph.

Question 13

Graph

Answer 13

Consists of a set of vertices and a set of edges.

Question 14

Graph isomorphism
between two simple
graphs G and H

Answer 14

A one-to-one correspondence between vertices of G and H such that a pair of
vertices in G is adjacent if and only if the corresponding pair in H is adjacent.

Question 15

Hamiltonian cycle

Answer 15

A cycle that contains all the vertices of the graph.

Question 16

Hamiltonian path

Answer 16

A path that contains all the vertices of the graph.

Question 17

Loop

Answer 17

An edge joining a vertex to itself.

Question 18

Minimum spanning

tree

Answer 18

A spanning tree of a weighted graph that has the minimum total weight.

Question 19

Multiple edges

Answer 19

Occur if more than one edge joins the same pair of vertices.

Question 20

Path

Answer 20

A walk with no repeated vertices.

Question 21

Planar graph

Answer 21

A graph that can be drawn in the plane without any edge crossing another.

Question 22

Simple graph

Answer 22

A graph without loops or multiple edges.

Question 23

Spanning tree of a

graph

Answer 23

A subgraph that is a tree, containing every vertex of the graph.

Question 24

Subgraph

Answer 24

A graph within a graph.

Question 25

Trail

Answer 25

A walk in which no edge appears more than once.

Question 26

Tree

Answer 26

A connected graph that contains no cycles.

Question 27

Walk

Answer 27

A sequence of linked edges.

Question 28

Weighted graph

Answer 28

A graph in which each edge is allocated a number or weight.

Question 29

Weighted tree

Answer 29

A tree in which each edge is allocated a number or weight.

Question 30

Chinese postman problem

Answer 30

To determine a cycle where each vertex is visited once only, returning to the original vertex of least total weight

Question 31

Travelling salesman problem

Answer 31

To determine the shortest route that visits each vertex and returns to the original vertex, of least weight.

Question 32

Pigeon Hole Principle

Answer 32

If kn+1 objects (where k, n are members of the positive integers) are divided into n groups, there will be a group that contains at least k+1 objects.

Question 33

The Fundamental Theorem of Arithmetic

Answer 33

Every number >1 can be written as a unique product of prime numbers.