Discrete definitions

Question 1

Vertice

Answer 1

Point on a graph

Question 2

Node

Answer 2

Point on a graph

Question 3

Edge

Answer 3

Line on a graph

Question 4

Arc

Answer 4

Line on a graph

Question 5

Degree

Answer 5

How many edges/arcs connected to vertice/node

Question 6

Order

Answer 6

How many edges/arcs connected to vertice/node

Question 7

Valency

Answer 7

How many edges/arcs connected to vertice/node

Question 8

Isomorphic

Answer 8

Graphs with same vertices and edges

Question 9

Network

Answer 9

Graph with weights (values) on the edges

Question 10

Walk

Answer 10

Sequence of edges where end vertex of one edge is the start vertex of the next

Question 11

Trail

Answer 11

Walk (sequence of edges that just follow onto each other) where none of the edges are repeated

Question 12

Path

Answer 12

Trail (sequence of edges where no edges are repeated) where none of the vertices are repeated

Question 13

Cycle

Answer 13

Closed (end joins the beginning) path (sequence of edges where no edges and no vertices are repeated)
Same cycle has same edges, can be forwards backwards order, start from different vertex doesn’t matter still same cycle as long as edges are the same

Question 14

Circuit

Answer 14

Closed (end joins the beginning) path (sequence of edges where no edges and no vertices are repeated)
Same cycle has same edges, can be forwards backwards order, start from different vertex doesn’t matter still same cycle as long as edges are the same

Question 15

Simple graph

Answer 15

Graph with no loops, at most one edge connecting any pair of vertices

Question 16

Connected vertices

Answer 16

vertices with a path (sequence of edges where no vertices or edges are repeated) between them

Question 17

Connected graph

Answer 17

Graph where all pairs of vertices are connected (have a sequence of edges with no repeated vertices or edges in between them)

Question 18

Tree

Answer 18

Connected graph (graph where all pairs of vertices can be joined by a sequence of edges with no repeated vertices or edges) with no cycles (sequence of edges with no repeated vertices or edges, where the end joins the beginning)
Planar (can be drawn so that no arcs cross)

Question 19

Complete graph

Answer 19

Every pair of vertices is connected by a single edge, so all the vertices are connected to each other
never planar (never can be drawn so that no arcs cross)

Question 20

Planar graph

Answer 20

One that can be drawn so that none of the arcs cross

Question 21

Hamiltonian cycle

Answer 21

Cycle (sequence of edges with no repeated edges or vertices whose end meets the beginning) that visits all the vertices of the graph. Visits each vertex exactly once then returns to start vertex.