Decision

Question 1

Graph

Answer 1

Consists of points (called vertices or nodes) which are connected by lines (edges or arcs)

Question 2

Weighted Graph

Answer 2

A graph with number or ‘weights’ associated with each edge

Question 3

Subgraph

Answer 3

A graph, each of whose vertices belongs to the original graph and each of whose edges belongs to the original graph. (It was part of the original graph)

Question 4

Degree

Answer 4

Also called valency or order, the degree of a vertex is the number of edges incident to it

Question 5

Walk

Answer 5

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

Question 6

Path

Answer 6

A walk in which no vertex is listed more than once

Question 7

Trail

Answer 7

A walk in which no edge is visited more than once

Question 8

Cycle

Answer 8

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

Question 9

Hamiltonian Cycle

Answer 9

A cycle that includes every vertex

Question 10

Loop

Answer 10

An edge that starts and finishes at the same vertex

Question 11

Simple Graph

Answer 11

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

Question 12

Directed Graph (Digraph)

Answer 12

When the edges of a graph a direction associated with them

Question 13

Handshaking Lemma

Answer 13

In any undirected graph, the sum of the degrees of the vertices is equal to 2 x the number of edges and hence, the number of odd nodes must be even

Question 14

Tree

Answer 14

A connected graph with no cycles

Question 15

Spanning Tree

Answer 15

Subgraph which includes all the vertices of the original graph but is also a tree

Question 16

Complete Graph

Answer 16

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