Key Terms

Question 1

What are the ‘points’ and the ‘lines’ on a graph called?

Answer 1

• The ‘points are referred to as nodes or vertices.

- The ‘lines’ are referred to as edges or arcs.

Question 2

Define a network:

Answer 2

A network is a graph with weighted edges. (A weighted edge is an edge with values assigned to it, such as a line being 72 km).

Question 3

What is the degree/valency/order of a point?

Answer 3

The number of edges connected to the vertex.

Note: depending on the order of a node it can be odd or even.

Question 4

How would you describe two graphs that have equal amounts of edges, nodes and degrees?

Answer 4

These two graphs would be describes as ‘isomorphic’.

Question 5

Describe the difference between a walk and trail:

Answer 5

• A walk is a sequence of edges where the end vertex of one edge is the start vertex of the next.
• A trail is a sequence of edges where the end vertex of one edge is the start vertex of the next but where none of the edges are repeated. (A trail is a walk where none of the edges are repeated).

Question 6

What is a path?

Answer 6

• A path is a sequence of edges where the end of one edge is the start vertex of the next but none of the edges or vertices are repeated. (A path is a trail where none of the vertices are repeated).

Question 7

Define a cycle or circuit:

Answer 7

• A cycle/circuit is a closed sequence of edges where the end of one edge is the start vertex of the next but where no edges or vertices are repeated. (A cycle/circuit is a closed path)

Closed - The end of the path joins back to the beginning).

Question 8

What is a loop?

Answer 8

An edge connecting a node to itself.

Question 9

Describe a simple graph:

Answer 9

The graph has no loops and at most one edge connected any pair of vertices.

Question 10

What is a tree?

Answer 10

A tree is a connected graph with no cycles.

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

Question 11

What is a ‘complete’ graph?

Answer 11

A complete graph is one in which every pair of vertices is connected by a single edge.

Question 12

A complete graph with ‘n’ vertices is referred to as…?

Answer 12

K (subscript) n

Question 13

Define a planar graph:

Answer 13

A planar graph is one that can be drawn so that none of the arcs cross.

Question 14

What is a graph:

Answer 14

A graph consists of points (called nodes or vertices ) which are connected by lines (called edges or arcs).

Question 15

Describe a directed graph:

Answer 15

If the edges/arcs on a graph have directions on them they are called directed edges, making the graph a directed graph (or a digraph).

Question 16

Explain Euler’s handshaking lemme

Answer 16

In any UNDIRECTED graph, the sum of the degrees of the vertices is equal to 2 * the number of the edges. Consequently, the number of odd nodes must be even.

Question 17

What is a Hamiltonian cycle?

Answer 17

A cycle that passes through EVERY node once before returning to the starting vertex.

• One possible way to check if a cycle is Hamiltonian is to count the edges and vertices (which should be equal).