D1-ch.2 Definitions

Question 1

Cycle or circuit

Answer 1

is a closed path – the end vertex of the last edge is the start
vertex of the first edge.

Question 2

Hamiltonian cycle

Answer 2

is a cycle that passes through every vertex of the graph once
and only once, and returns to its start vertex.

Question 3

Eulerian cycle

Answer 3

is a cycle that includes every edge of a graph exactly once.

Question 4

Edge set

Answer 4

is the set of all edges.

Question 5

Vertex set

Answer 5

is the set of all vertices.

Question 6

Path

Answer 6

is 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 7

Connected

Answer 7

• Two vertices are connected if there is a path between them.
• A graph is connected if all of its vertices are connected.

Question 8

Loop

Answer 8

•An edge with the same vertex at each end

Question 9

Simple graph

Answer 9

does not contain any ‘parallel’ arcs nor any loops.

Question 10

Valency, degree or order

Answer 10

the number of edges connected to a node

Question 11

Diagraph

Answer 11

•If the edges of a graph have a direction associated with them, they are known as
directed edges

Question 12

Tree

Answer 12

connected graph with no cycles (e.g. family trees, probability tree
diagrams).

Question 13

Spanning tree

Answer 13

is a subgraph that includes all the vertices of G and is

also a tree.

Question 14

Complete graph Kn

Answer 14

has n vertices where all vertices are connected by an edge to
each of the other vertices

Question 15

Bipartite graph

Answer 15

consists of two sets of vertices X and Y. The edges only join
vertices in X to vertices in Y – i.e. not vertices within a set. If there are r vertices in X
and s vertices in Y and every vertex in X is joined to every vertex in Y, then the graph
is called Kr,s.

Question 16

Planar graph

Answer 16

a graph which can be drawn in a plane in such a way that no two
edges meet each other, except at a vertex to which they are both incident.

Question 17

Isomorphic graphs

Answer 17

if they have the same number of vertices

and the degrees of the corresponding vertices are the same.

Question 18

Network

Answer 18

•A graph with weighted edges
•(The weights can refer to any quantity relating a pair of edges; e.g. distance, time,
cost, etc.)

Question 19

Graph

Answer 19

A graph G consists of nodes which are connected by edges.

Question 20

Subgraph

Answer 20

Is a graph, each of whose vertices and edges belongs to a larger graph.

Question 21

Minimum spanning tree

Answer 21

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

Question 22

Matching

Answer 22

Is a subset of edges from a bipartite graph, such that no two edges in the subset have a common vertex.

Question 23

Complete matching

Answer 23

Is a matching which consists of n vertices in each set and n edges.

Question 24

Maximal matching

Answer 24

Is a matching in which the number of edges is as large as possible.