Practice Maths

L37 — Introduction to Networks

Key Terms

Vertex (node)
A point in a graph representing a location, object, or entity.
Edge (arc)
A connection between two vertices; can be directed (one-way) or undirected (two-way).
Degree
The number of edges connected to a vertex; the sum of all degrees = 2 × number of edges (handshaking lemma).
Weighted graph
A graph where each edge has a numerical value (weight) such as distance, time, or cost.
Path
A sequence of vertices connected by edges with no repeated vertices or edges.
Euler circuit
A path that starts and ends at the same vertex and traverses every edge exactly once — possible only if every vertex has even degree.

Graph terminology

TermDefinitionExample
Vertex (node)A point in the graphA city on a map
Edge (arc)A connection between two verticesA road between cities
DegreeNumber of edges at a vertexdeg(A) = 3 means 3 edges meet at A
LoopAn edge connecting a vertex to itselfAdds 2 to the degree
Weighted graphEdges have numerical values (weights)Distance, cost, time
Directed graphEdges have a direction (arrows)One-way streets

Handshaking lemma

Sum of all degrees = 2 × number of edges

Consequence: the number of odd-degree vertices is always even.

Types of graphs

TypeDescription
Simple graphNo loops, no multiple edges between same pair of vertices
Complete graph KnEvery pair of vertices connected; has n(n−1)/2 edges
Connected graphA path exists between every pair of vertices
TreeConnected graph with no cycles; has n−1 edges for n vertices
Bipartite graphVertices split into two groups; edges only between groups
A B C D E deg=3 deg=3 deg=3 deg=3 deg=2 Sum of degrees = 3+3+3+3+2 = 14 = 2×7 edges
A graph with 5 vertices and 7 edges. Handshaking lemma: sum of degrees = 14 = 2 × 7.
Hot Tip: The handshaking lemma is a quick error-check: the sum of all vertex degrees must always be even and equal to 2 × (number of edges). If your degree sum is odd, you have a counting error.

Worked Example 1 — Reading a graph

For the graph in the Key Ideas diagram, state the number of vertices, edges, and the degree of each vertex.

Vertices: 5 (A, B, C, D, E). Edges: 7.

deg(A) = 3, deg(B) = 3, deg(C) = 3, deg(D) = 3, deg(E) = 2.

Check: 3+3+3+3+2 = 14 = 2×7. ✓

Worked Example 2 — Handshaking lemma

A graph has 6 vertices with degrees 1, 2, 3, 3, 4, 5. How many edges does it have?

Sum of degrees = 1+2+3+3+4+5 = 18.

Number of edges = 18/2 = 9.

Worked Example 3 — Drawing a graph

Draw a graph with vertices P, Q, R, S where P–Q, P–R, Q–S, R–S, Q–R are the edges.

5 edges. deg(P)=2, deg(Q)=3, deg(R)=3, deg(S)=2. Sum = 10 = 2×5. ✓

Worked Example 4 — Complete graph

How many edges does K5 have? What is the degree of each vertex?

Edges = 5(5−1)/2 = 10. Every vertex connects to 4 others, so deg = 4 for all vertices.

Worked Example 5 — Real-world modelling

Four towns: Alphaville (A), Betaburg (B), Gamma City (C), Deltatown (D). Roads: A–B, A–C, B–C, B–D, C–D. Draw the graph and find the degree of each town.

deg(A)=2, deg(B)=3, deg(C)=3, deg(D)=2. Sum = 10 = 2×5 edges. ✓

The graph is connected — a path exists between any two towns.

See Answers ➔

  1. Basic graph terminology. Fluency

    A graph has vertices A, B, C, D, E with edges AB, AC, AD, BC, CE, DE.

    • (a) How many vertices and edges does the graph have?
    • (b) Find the degree of each vertex.
    • (c) Verify the handshaking lemma.
    • (d) How many odd-degree vertices are there?

  2. Handshaking lemma. Fluency

    • (a) A graph has 5 edges. What is the sum of all vertex degrees?
    • (b) A graph has vertices with degrees 2, 3, 4, 5, 2. How many edges are there?
    • (c) Can a graph have exactly 3 vertices of odd degree? Explain.
    • (d) A graph has 4 vertices each of degree 3. How many edges does it have?

  3. Complete graphs and trees. Fluency

    • (a) How many edges does K6 have?
    • (b) A tree has 8 vertices. How many edges does it have?
    • (c) A complete graph Kn has 21 edges. Find n.
    • (d) True or false: every tree is connected. Explain.

  4. Graph properties. Fluency

    • (a) What is the difference between a directed and an undirected graph? Give a real example of each.
    • (b) A graph has vertices with degrees 4, 4, 4, 4. State the number of edges and name the graph (Kn for some n).
    • (c) Can two different graphs have the same degree sequence? Give an example or explain why not.
    • (d) A weighted graph has edges AB=5, AC=3, BC=8, CD=2. Find the minimum total weight path from A to D that visits every vertex.

  5. Reading a weighted network. Understanding

    The diagram shows a weighted network of roads between towns (weights in km).

    8 6 5 10 7 4 P Q R S T
    Weighted road network (distances in km).
    • (a) State the number of vertices and edges.
    • (b) Find the degree of each vertex and verify the handshaking lemma.
    • (c) Find the total weight of all edges combined.
    • (d) List all paths from P to T and find the shortest one.

  6. Adjacency and connectivity. Understanding

    • (a) Write the adjacency list for the graph in Q5.
    • (b) Is the graph in Q5 connected? Explain.
    • (c) What is the minimum number of edges you must add to make an isolated vertex (a vertex with degree 0) connected to the rest of the graph?
    • (d) A graph has 5 vertices and is connected. What is the minimum number of edges it can have?

  7. Real-world graph modelling. Understanding

    • (a) Model a social network where 5 people each follow every other person on a platform. What type of graph is this? How many edges?
    • (b) A company has 4 offices. Each office must be directly connected to at least 2 others for redundancy. Draw a possible graph satisfying this requirement.
    • (c) An airline has routes: Syd–Mel (90 min), Syd–Bne (90 min), Mel–Ade (70 min), Bne–Ade (130 min). Draw the weighted graph. Which city has the highest degree?
    • (d) In (c), is the graph connected? Can you travel from Ade to Syd using the available routes?

  8. Graph types. Understanding

    • (a) Draw a bipartite graph where set X = {1, 2, 3} and set Y = {a, b}, with every vertex in X connected to every vertex in Y.
    • (b) How many edges does this bipartite graph have?
    • (c) Explain why K3 (three mutually connected vertices) is NOT bipartite.
    • (d) A graph has a loop at vertex V. What is the minimum degree of V?

  9. Degree sequences and graph construction. Problem Solving

    • (a) Is the sequence (3, 3, 2, 2, 2) a valid degree sequence for a simple graph? If so, construct it.
    • (b) Is the sequence (4, 3, 3, 2, 2) valid? Why or why not?
    • (c) Is the sequence (3, 3, 3, 1) valid? Construct the graph or explain why it’s impossible.
    • (d) A graph has n vertices, all with degree n − 1. Identify the graph and write a formula for the number of edges in terms of n.

  10. Network design. Problem Solving

    A local council wants to install fibre optic cable connecting 6 suburbs: A, B, C, D, E, F. Possible connections and costs ($000s): A–B=12, A–C=8, B–C=5, B–D=9, C–D=11, C–E=7, D–F=6, E–F=10.

    • (a) Draw the weighted graph.
    • (b) The council wants all suburbs connected. What is the minimum number of edges needed?
    • (c) Find the total cost if ALL possible edges are installed.
    • (d) If budget is $35 000, which edges must be prioritised to keep all suburbs connected? (Try to minimise total cost.)