Graphs and networks: the language

Basic words

A graph is a set of vertices (nodes) joined by edges (arcs). A network (weighted graph) has a number, the weight, on each edge, such as a distance or cost. The degree (valency) of a vertex is the number of edge ends at it. A digraph has directed edges (arrows).

Walks, paths, cycles

• Walk: a route along edges.
• Path: a walk with no repeated vertex.
• Cycle: a closed path that returns to its start without repeating any other vertex.
• Hamiltonian cycle: a cycle that visits every vertex exactly once.
• Connected: there is a path between every pair of vertices.

Types of graph

• Simple: no loops and at most one edge between any pair of vertices.
• Tree: connected with no cycles; a tree on n vertices has n - 1 edges.
• Spanning tree: a subgraph that is a tree and includes every vertex.
• Complete graph K_n: every vertex joined to every other; K_n has n(n - 1)/2 edges.
• Planar: can be drawn with no edges crossing.
• Isomorphic: two graphs that show exactly the same connections between vertices, drawn differently.

Handshaking and matrices

Each edge has two ends, so the sum of the degrees = 2 × the number of edges, and there is always an even number of odd vertices. A network can be stored as a distance matrix: the entry in row X, column Y is the weight of edge XY, with a dash where there is no edge.

Worked example

A graph has vertices of degrees 3, 3, 2, 4, 2. How many edges does it have?

1. Sum of degrees = 3 + 3 + 2 + 4 + 2 = 14
2. Edges = 14 ÷ 2 = 7

Answer: 7 edges

Check yourself

1. How many edges does the complete graph K_7 have?
   Show answer

   21. n(n - 1)/2 = 7 × 6/2 = 21.

2. A spanning tree is drawn on a network with 12 vertices. How many edges does it have?
   Show answer

   11. A tree on n vertices has n - 1 = 11 edges.

3. A graph has 9 edges. What is the sum of the degrees of its vertices?
   Show answer

   18. Each edge adds 2 to the degree total: 2 × 9 = 18.

4. Why can a graph not have exactly three odd vertices?
   • Odd vertices always come in groups of four
   • A graph must have at least one even vertex
   • Three vertices cannot be connected
   • The degree sum is even, so the number of odd vertices must be even
   Show answer

   The degree sum is even, so the number of odd vertices must be even. Sum of degrees = 2 × edges is even. An odd number of odd degrees would make the sum odd.

5. What is the difference between a path and a walk?
   • A path must return to its start
   • A path does not repeat any vertex
   • A path uses every edge
   • A path must use the shortest edges
   Show answer

   A path does not repeat any vertex. Any route along edges is a walk; a path has no repeated vertices.

6. What is a Hamiltonian cycle?
   • A route that uses every edge exactly once
   • A tree that includes every vertex
   • A cycle with the least total weight
   • A cycle that visits every vertex exactly once
   Show answer

   A cycle that visits every vertex exactly once. Hamiltonian cycles are about vertices; they are the tours in the travelling salesman problem.

7. Which graph is NOT simple?
   • A tree
   • A graph with two edges joining A to B
   • The complete graph K_4
   • A cycle on five vertices
   Show answer

   A graph with two edges joining A to B. A simple graph has no loops and no multiple edges.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Level in Mathematics specification (issue 3)
• Pearson Edexcel IAL Decision Mathematics 1 scheme of work

Last updated 7 November 2026. Spotted a mistake? Tell us.