Chapter 2

Question 1

Graph

Answer 1

Consists of vertices which are connected by arcs.

Question 2

Weighted grpah

Answer 2

Numbers associated to each arc.

Question 3

Subgraph

Answer 3

Part of the original graph.

Question 4

Degree/valency/order

Answer 4

Number of edges incident to it

Question 5

Walk

Answer 5

A route through a graph along edges fron one vertex to the next.

Question 6

Path

Answer 6

A walk from in which no vertex is visited 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 vetex and no other verted is visited more than once.

Question 9

Hamiltonian cycle

Answer 9

Cycle that includes every vertrx.

Question 10

Loop

Answer 10

Edge thag starts and finishes at the same vertex

Question 11

Simple graph

Answer 11

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

Question 12

Digraph

Answer 12

Directed graph/edges have a direction associated with them.

Question 13

Euler’s handshaking lemma

Answer 13

Sum of the degrees of the vertices is equal to 2x(number of edges)

Question 14

Tree

Answer 14

Connected graph with no cycles.

Question 15

Spanning tree

Answer 15

Subgraph which includes all ther vertices of the original graph and is alo a tree

Question 16

Complete graph

Answer 16

Graph which every vertex is directly connected by a single edge to each of the other vertices.

Question 17

Isomorphic graph

Answer 17

Graphs which show the same information but may be drawn differently

Question 18

Adjacency matrix

Answer 18

Describe the number of arcs joining the corresponding vertices.

Question 19

Distance matrix

Answer 19

Entries represent the weight of each arc.

Question 20

Planar graph

Answer 20

A graph that can be drawn in a plane such that no two edges meet except at a vertex.