AS Decision - 2: Graphs and Networks

Question 1

Subgraph

Answer 1

Part of the original graph

Question 2

Degree/Valency/Order

Answer 2

The number of edges incident to a vertex

Question 3

A Walk

Answer 3

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

Question 4

A Path

Answer 4

a walk where no vertex is visited more than once

Question 5

A Trail

Answer 5

a walk where no edge is visited more than once

Question 6

A Cycle

Answer 6

a walk where end vertex = start vertex and no other vertex is visited more than once

Question 7

A Hamiltonian Cycle

Answer 7

a cycle which includes every vertex

Question 8

Simple Graph

Answer 8

• no loops
• at most one edge connecting any pair of vertices

Question 9

Euler’s Handshaking Lemma

Answer 9

in any undirected graph, the sum of degrees of vertices is equal to 2x the number of edges

Question 10

Tree

Answer 10

connected graph with no cycles

Question 11

Spanning Tree

Answer 11

• tree
• subgraph
• includes all vertices

Question 12

Complete Graph

Answer 12

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

Question 13

Isomorphic Graph

Answer 13

a graph which shows the same information but is drawn differently