Networks, Paths & Connectedness
Network Vocabulary
Draw a line from each network term to its correct definition.
Degree of a Vertex
Circle the correct degree for the described vertex.
Vertex A is connected to vertices B, C, and D by one edge each
Vertex P has edges to Q, R, S, T, and also a loop back to itself
Vertex X is connected to Y by two separate edges, and to Z by one edge
An isolated vertex with no edges
Counting Vertices & Edges
Circle the correct count of vertices and edges for each network description.
A triangle (three points connected in a cycle)
A square (four points connected in a cycle)
A square with both diagonals drawn
Five cities where every pair is directly connected by a road
Classify Real-World Networks
Sort each real-world network into the correct type.
Connected or Disconnected?
Sort each graph description into Connected or Disconnected.
Path or Circuit?
Circle whether each route is a Path (starts and ends at different vertices), a Circuit (starts and ends at the same vertex), or Neither. Assume no edge is repeated unless stated.
A → B → C → D
A → B → C → D → A
P → Q → R → Q → S (edge Q–R is used twice)
X → Y → Z → X
Is It a Tree?
A tree is a connected graph with no circuits. Circle whether each description is a tree.
A graph with 4 vertices and 3 edges that is connected and has no circuits
A triangle (3 vertices, 3 edges)
A graph with 5 vertices and 4 edges that is connected
Two separate edges (A–B and C–D) with no connection between them
Planar or Non-Planar?
A planar graph can be drawn on a flat surface with no edges crossing. Sort each graph.
Euler Path Possible?
An Euler path uses every edge exactly once. It exists when a connected graph has exactly 0 or 2 vertices of odd degree. Circle the correct answer.
Vertex degrees: 2, 2, 2, 2 (a square)
Vertex degrees: 3, 3, 2, 2
Vertex degrees: 1, 1, 2, 2, 2
Vertex degrees: 3, 3, 3, 1
Euler Circuit Possible?
An Euler circuit uses every edge exactly once and returns to the start. It exists when every vertex has even degree and the graph is connected. Circle the correct answer.
Vertex degrees: 4, 2, 4, 2
Vertex degrees: 2, 2, 2 (a triangle)
Vertex degrees: 3, 3, 2, 2, 2
Vertex degrees: 4, 4, 4, 4
Odd & Even Degree Vertices
Count the number of odd-degree and even-degree vertices in each graph. Circle the correct count.
A triangle: vertex degrees 2, 2, 2
A square with one diagonal: vertex degrees 3, 3, 2, 2
K₄ (complete graph on 4 vertices): vertex degrees 3, 3, 3, 3
A path graph P₅ (5 vertices in a line): vertex degrees 1, 2, 2, 2, 1
Shortest Path Algorithm
Put the steps of Dijkstra's shortest-path algorithm in the correct order.
Finding an Euler Path
Put the steps in order to find an Euler path in a connected graph with exactly 2 odd-degree vertices.
Euler Classification
Sort each set of vertex degrees by whether the connected graph has an Euler circuit, an Euler path (not circuit), or neither.
Hamiltonian Paths
A Hamiltonian path visits every vertex exactly once. Circle the correct answer for each question.
Does a complete graph K₅ (5 vertices, every pair connected) have a Hamiltonian path?
A path graph P₄ (4 vertices in a line: A–B–C–D). Does a Hamiltonian path exist?
True or false: Every graph with a Hamiltonian circuit also has a Hamiltonian path.
True or false: Every graph with an Euler circuit also has a Hamiltonian circuit.
Minimum Spanning Trees
A minimum spanning tree (MST) connects all vertices with the smallest total edge weight and no circuits. Circle the correct answer.
A connected graph has 6 vertices. How many edges does its spanning tree have?
In Prim's algorithm, at each step you add:
In Kruskal's algorithm, at each step you add:
A graph has 8 vertices. Can its MST contain a circuit?
Vertex Degrees & Euler Paths
Match each scenario to the correct conclusion. Remember: 0 odd-degree vertices → Euler circuit; 2 odd-degree vertices → Euler path; any other count → neither. The graph must also be connected.
Shortest vs Longest Path
A network has vertices A, B, C, D, E with weighted edges: A–B = 3, A–C = 7, B–C = 2, B–D = 5, C–D = 1, C–E = 4, D–E = 6. Sort each route from A to E into Short (total ≤ 10) or Long (total > 10).
Shortest Route Problem
Draw the network and find the shortest route.
Six towns A–F are connected by roads with these distances (km): A–B = 4, A–C = 2, B–C = 1, B–D = 5, C–D = 8, C–E = 10, D–E = 2, D–F = 6, E–F = 3. (a) Draw the weighted network. (b) Find the shortest route from A to F. Show your working by listing all reasonable paths and their total distances. (Hint: consider A → C → B → D → E → F = 2 + 1 + 5 + 2 + 3 = 13 km — can you find a shorter one?)
Delivery Driver – Euler Path
Solve this Euler path problem. Show all working.
A postal worker must walk along every street in a small neighbourhood exactly once. The streets form a network with vertices A, B, C, D, E and edges: A–B, A–C, A–D, B–C, B–D, C–D, D–E. (a) Write down the degree of each vertex. (b) How many vertices have odd degree? (c) Explain whether an Euler path or Euler circuit exists. (d) If an Euler path exists, find one and write out the route.
The Königsberg Bridge Problem
Investigate the famous problem that started graph theory.
The city of Königsberg had 4 land masses (A, B, C, D) connected by 7 bridges: A–B (2 bridges), A–C (2 bridges), A–D (1 bridge), B–D (1 bridge), C–D (1 bridge). (a) Draw a network with vertices for land masses and edges for bridges. (b) Write down the degree of each vertex. (c) How many odd-degree vertices are there? (d) Explain why it is impossible to walk across each bridge exactly once. (e) What is the minimum number of bridges you would need to add or remove to make an Euler circuit possible?
Design a Road Network
Design and analyse a road network using minimum spanning trees.
A developer is planning roads between 6 new housing estates (V₁ to V₆). The possible roads and costs (in $000s) are: V₁–V₂ = 120, V₁–V₃ = 200, V₂–V₃ = 80, V₂–V₄ = 150, V₃–V₄ = 90, V₃–V₅ = 110, V₄–V₅ = 70, V₄–V₆ = 130, V₅–V₆ = 100. (a) Draw the weighted network. (b) Use Kruskal's algorithm to find the minimum spanning tree: list edges in ascending weight order and select each if it doesn't form a circuit. Show each step. (c) What is the total cost of the minimum spanning tree? (d) How many edges does the MST have? Explain why this equals n − 1 = 5.
Social Network Analysis
Model and analyse a social network.
In a class of 7 students (A–G), the following friendships exist: A–B, A–C, A–D, B–C, B–E, C–D, C–F, D–G, E–F, F–G. (a) Draw the friendship network. (b) Find the degree of each vertex. Which student has the most connections? (c) Is the network connected? Justify your answer. (d) Can you find a Hamiltonian path (visiting every student exactly once)? Write one out. (e) The sum of all vertex degrees should equal twice the number of edges. Verify this for the network.
True or False: Network Properties
Circle True or False for each statement about networks.
The sum of all vertex degrees in any graph equals twice the number of edges.
A connected graph with n vertices and n − 1 edges must be a tree.
Every Euler circuit is also an Euler path.
A graph can have exactly 1 vertex of odd degree.
A tree with 10 vertices has exactly 9 edges.
If a connected graph has all vertices of even degree, it must have an Euler circuit.
Minimum Spanning Tree – Cable Network
Find the minimum spanning tree for a cable network.
An internet provider needs to connect 5 buildings (A–E) using the least cable. Available connections and cable lengths (m): A–B = 50, A–C = 80, A–D = 120, B–C = 40, B–D = 70, B–E = 90, C–D = 60, C–E = 55, D–E = 45. (a) Draw the weighted graph. (b) Apply Kruskal's algorithm: list edges in weight order (B–C 40, D–E 45, A–B 50, C–E 55, C–D 60, B–D 70, A–C 80, B–E 90, A–D 120), and select each if it doesn't create a circuit. Show each step. (c) Draw the MST and state its total cable length. (d) How many edges were selected? Explain why this equals n − 1 = 4.
Critical Path Analysis
Apply network analysis to a simple project.
A student project has these tasks and durations: A (2 days, no prerequisites), B (3 days, no prerequisites), C (4 days, requires A), D (2 days, requires A and B), E (3 days, requires C), F (1 day, requires D and E). (a) Draw an activity network (directed graph) showing task dependencies. (b) Find the earliest start time for each task. (c) What is the minimum total project duration? (d) Identify the critical path — the longest path through the network. Verify by checking all paths: A → C → E → F = 2 + 4 + 3 + 1 = 10 days; A → D → F = 2 + 2 + 1 = 5 days; B → D → F = 3 + 2 + 1 = 6 days. The critical path is A → C → E → F = 10 days.
Home Room Network
Create and analyse a network of your home.
- 1Draw a floor plan of your home. Represent each room (including hallways and outdoors) as a vertex, and each doorway or opening as an edge.
- 2Write down the degree of each vertex. Which room has the most connections?
- 3Is your home network connected? (Can you reach every room from every other room?)
- 4Determine whether an Euler path exists — can you walk through every doorway exactly once? Check by counting odd-degree vertices.
- 5If an Euler path is possible, find one and record the route. If not, explain which doorways you would need to add or remove.
Transport Network Investigation
Analyse a real transport network in your area.
- 1Find a local bus, train, or cycling route map. Identify 8–12 stops or stations as vertices and the routes connecting them as edges.
- 2Draw the transport network. Label each edge with the approximate travel time (in minutes) between stops.
- 3Calculate the degree of each vertex. Which station is the busiest hub?
- 4Using your weighted network, find the shortest travel-time route between two stations that are not directly connected.
- 5Does an Euler path or circuit exist in your transport network? Explain your reasoning using vertex degrees.
Graph Theory Vocabulary
Define and apply key graph theory vocabulary.
For a network with 6 vertices and 9 edges, state: (a) What is meant by the 'degree' of a vertex? (b) What does Euler's handshaking lemma state? Verify it for this network. (c) What is the difference between a path, a trail, and a walk in a graph?
Network Theory Terms — Definitions
Draw a line from each graph theory term to its correct definition.
Eulerian Paths and Circuits
Circle the correct answer about Eulerian paths and circuits.
An Eulerian circuit exists in a graph if and only if:
An Eulerian path (but not circuit) exists when:
A graph has vertices with degrees 3, 3, 4, 4, 2. It:
The Königsberg Bridge problem showed that the original layout had:
Shortest Path — Dijkstra's Algorithm
Apply Dijkstra's algorithm to find the shortest path.
In a network of towns A–F, the edge weights represent travel time in minutes: A–B: 10, A–C: 15, B–D: 12, B–C: 5, C–E: 20, D–E: 8, D–F: 15, E–F: 10. Find the shortest path from A to F using Dijkstra's method. Show the table of visited vertices and distances at each step.
Connected vs Disconnected Graphs
Sort each description: Connected Graph or Disconnected Graph.
Minimum Spanning Trees
Find minimum spanning trees using Kruskal's algorithm.
A telecommunications company needs to connect 5 buildings with fibre cable. Possible connections and costs (in $1,000): A–B: 3, A–C: 5, B–C: 4, B–D: 6, C–D: 2, C–E: 8, D–E: 4. Use Kruskal's algorithm (add edges in order of weight, skip if it creates a cycle) to find the minimum spanning tree. What is the total minimum cost?
Hamiltonian Paths and Circuits
Circle the correct answer about Hamiltonian paths and circuits.
A Hamiltonian circuit:
The Travelling Salesman Problem (TSP) seeks:
Unlike Eulerian circuits, determining if a Hamiltonian circuit exists is:
Network Applications — Project Planning
Apply network analysis to project scheduling.
A building project has tasks with dependencies: • A (2 days): clear site • B (3 days): lay foundation — depends on A • C (1 day): order materials — can start with A • D (4 days): framing — depends on B and C • E (2 days): roofing — depends on D Draw the network diagram. Find the critical path (longest path from start to finish). What is the minimum project duration?
Algorithm Name to Purpose
Draw a line from each algorithm to its purpose in network analysis.
Directed vs Undirected Graphs
Compare directed (digraphs) and undirected graphs.
Explain the difference between a directed and undirected graph. Give one real-world example of each. In what type of network is direction important? Why?
Draw and describe a directed graph for: 'Stephanie follows Alice on social media, Alice follows Ben, Ben follows Stephanie, and Alice follows Cara.' Who has the most followers? Who follows the most people?
Real-World Networks — Type Classification
Sort each real-world network: Transport Network, Social Network, Communication Network, or Utility Network.
Map Your Local Network
Create and analyse a real network from your local area.
- 1Draw a simplified road network of your suburb. Include 6–10 intersections as vertices and roads as edges. Estimate distances from Google Maps. Find the shortest route from your home to school using Dijkstra's method.
- 2Create a 'friend network' graph for your household or extended family. Determine the degree of each person. Is the network connected? Who has the highest degree?
- 3Research the concept of 'Six Degrees of Separation.' Test it informally by trying to connect yourself to a famous person through a chain of real acquaintances. How many steps does it take?
Graph Matrices — Adjacency Matrix
Represent a graph using an adjacency matrix.
A graph has 4 vertices: A, B, C, D. Edges: A–B, A–C, B–C, B–D, C–D. Write the 4×4 adjacency matrix for this undirected graph. What does the sum of each row represent? What does squaring the adjacency matrix tell you?
Network Applications Researched
Tally the number of different network applications you research in one week.
| Item | Tally | Total |
|---|---|---|
Transport and logistics networks | ||
Social media networks | ||
Computer/internet networks | ||
Biological networks (food webs, neurons) | ||
Utility networks (power, water) |
Degree Sequence and Euler's Theorem
Use degree sequences to determine properties of a graph.
A graph has degree sequence (2, 3, 3, 4, 4, 6). (a) How many vertices does it have? (b) Using the handshaking lemma, how many edges does it have? (c) Does it have an Eulerian path? An Eulerian circuit? Justify your answer.
Bipartite Graphs
Circle the correct answer about bipartite graphs.
A bipartite graph has vertices split into two groups where:
A common real-world example of a bipartite graph is:
Every bipartite graph:
Network Vocabulary — Match the Term
Draw a line from each network term to its correct definition.
Euler Paths and Circuits
Apply Euler's theorems to real network problems.
State Euler's theorem for the existence of an Euler circuit (a path that uses every edge exactly once and returns to the start).
Draw a network with 5 vertices. Determine whether an Euler path or circuit exists. Justify your answer.
A town has 6 bridges connecting land masses. Apply Euler's theorem to determine if it is possible to cross all bridges exactly once. Show your working.
Research the Königsberg Bridge Problem. Write a short paragraph about how Euler solved it and its significance.
Classify Network Problems
Sort each problem into the type of network problem it represents.
Minimum Spanning Trees
Apply Kruskal's or Prim's algorithm to find minimum spanning trees.
Explain what a spanning tree is and why 'minimum' spanning trees are useful in network design.
A network has 5 cities with these connections and distances (in km): A–B: 4, A–C: 7, B–C: 3, B–D: 5, C–D: 2, D–E: 6, C–E: 8. Apply Kruskal's algorithm to find the minimum spanning tree. Show each step.
What is the total length of your minimum spanning tree? How much distance is saved compared to connecting all cities in a chain?
Network Problem Types Solved
Tally each type of network problem you solved during this unit.
| Item | Tally | Total |
|---|---|---|
Shortest path | ||
Euler path/circuit | ||
Minimum spanning tree | ||
Hamiltonian path | ||
Graph coloring |
Adjacency Matrices
Represent and interpret networks using adjacency matrices.
Draw a simple graph with 4 vertices (A, B, C, D) with edges AB, BC, CD, and AD. Write its adjacency matrix.
What does the entry in row i, column j of an adjacency matrix tell you about the graph?
If the adjacency matrix is symmetric, what does this tell you about the graph?
For a weighted graph (e.g. road distances), how would you modify the adjacency matrix? Give an example.
Properties of Special Graphs
Circle the correct answer about each special type of graph.
A complete graph with 5 vertices (K₅) has how many edges?
A tree with 8 vertices has how many edges?
Which graph type has exactly two possible vertex colourings?
Euler's formula for connected planar graphs is:
Networks in Real Life
Explore how network mathematics applies in technology, transport, and society.
- 1Draw a network diagram of the suburbs connected by train lines in your nearest city. Identify hubs (high-degree vertices).
- 2Research how the internet is structured as a network. Write a paragraph about redundancy and why it matters for reliability.
- 3Map the social connections in your household or class (who knows whom). Identify the most 'connected' person.
- 4Investigate how Google Maps or Apple Maps uses shortest-path algorithms. Write a brief summary of Dijkstra's algorithm.
- 5Research the 'six degrees of separation' idea. Conduct a small experiment by seeing how many steps connect you to a famous Australian.
Travelling Salesman Problem
Explore one of the most famous unsolved problems in computer science.
Describe the Travelling Salesman Problem (TSP) in your own words.
For 4 cities A, B, C, D with distances AB=10, AC=15, AD=20, BC=12, BD=8, CD=18, find the shortest round trip visiting all cities. List all possible routes and their total distances.
Explain why TSP becomes computationally hard as the number of cities grows. How many routes are there for n cities?
Research one approximation algorithm used to solve TSP in practice. Describe how it works.
Dijkstra's Algorithm Step-by-Step
Apply Dijkstra's shortest path algorithm manually.
Explain Dijkstra's algorithm in your own words. What problem does it solve?
Using this network: A–B: 4, A–C: 2, B–D: 5, C–B: 1, C–D: 8, D–E: 3. Apply Dijkstra's algorithm to find the shortest path from A to E. Show each step.
What is the shortest path and its total distance? List the vertices in order.
Critical Path Analysis
Apply critical path analysis to project planning.
Explain what a critical path is and why project managers use it.
A project has tasks: A(3 days, start first), B(2 days, after A), C(4 days, after A), D(1 day, after B and C), E(2 days, after D). Draw the network and find the critical path.
What is the minimum time to complete the project? Which tasks have float (slack time)?
If task C is delayed by 1 day, does this change the critical path? Explain.
Network Terminology — True or False
Sort each statement as True or False about networks.
Graph Colouring
Apply graph colouring to scheduling and map problems.
Explain what graph colouring means and what the chromatic number of a graph represents.
A university needs to schedule 5 exams. Subjects that share students cannot be scheduled at the same time. Draw a conflict graph and determine the minimum number of time slots needed.
Research the Four Colour Theorem. State the theorem and explain why it is significant.
Graph Theory — Historical Connections
Match each graph theory concept to its historical origin or key mathematician.