Introduction to Networks
Ausgrid engineers model Sydney's electricity grid as a network of vertices and edges. When a substation fails, they instantly know which nodes are most connected and which backup paths exist. This lesson introduces the mathematical language of networks — vertices, edges, degree — that underpins every algorithm in this module.
Practise this lesson
Three printable worksheets that build from foundations to mastery — or build your own from any module’s questions.
A road map shows cities connected by roads. Sydney has 5 roads connecting to it; Parramatta has 3; Penrith has 2; Liverpool has 4.
Before reading on — which city is "most connected"? How would you measure connectivity mathematically? Write your gut answer below.
A network (graph) has vertices (nodes) and edges (connections). The degree of a vertex equals the number of edges at that vertex. In a directed network, arrows show one-way connections; in an undirected network, all edges are two-way.
Vertex (node): a point in the network — represents a city, person, substation, etc.
Edge (arc): a connection between two vertices — may be directed (arrow) or undirected (line).
Degree: number of edges at a vertex. A loop at a vertex counts as 2 towards the degree.
Isolated vertex: a vertex with degree 0 — no edges connect to it.
Key facts
- Definitions: vertex, edge, degree, network
- Directed vs undirected networks
- Loop counts twice toward degree
Concepts
- Why degree measures connectivity
- When directed networks are needed
- What an isolated vertex means
Skills
- Draw a network from a description
- Find the degree of every vertex
- Classify a network as directed or undirected
A network consists of a set of vertices (dots) joined by edges (lines or arrows). To draw a network from a description:
- List all vertices and draw a dot for each.
- Read each connection and draw the corresponding edge.
- Add arrows if the network is directed.
- Label vertices with letters or names.
Example: "Four train stations A, B, C, D. Lines run: A–B, A–C, B–D, C–D." Draw four vertices, then add four edges connecting the stated pairs. Vertex A connects to B and C, so deg(A) = 2.
What to write in your book
- Network = vertices + edges. Vertex = dot. Edge = line or arrow.
- To draw: list vertices → draw dots → add edges for each connection → label.
- Position of dots on page doesn't change the network — only connections matter.
The degree of a vertex is the total number of edges connected to it. Rules:
- Each regular edge contributes 1 to the degree of each endpoint.
- A loop (an edge from a vertex to itself) contributes 2 to the degree of that vertex.
- A vertex with degree 0 is called an isolated vertex.
Example: In a network with edges A–B, A–C, A–D, A–A (loop): deg(A) = 1 + 1 + 1 + 2 = 5. Vertices B, C, D each have degree 1.
What to write in your book
- Degree = number of edges at a vertex. Count each edge that touches that vertex.
- Loop at vertex X: counts as 2 towards deg(X).
- Isolated vertex: degree = 0, no edges.
In a directed network (digraph), every edge has an arrow showing the direction of travel. In a directed network:
- In-degree of a vertex = number of arrows pointing INTO it.
- Out-degree of a vertex = number of arrows pointing OUT of it.
Real-life examples: one-way streets (can only drive one direction), social media following (A follows B doesn't mean B follows A), water mains (flow in one direction), web page hyperlinks.
Example: Edges A→B, A→C, B→D, C→D. deg-out(A) = 2, deg-in(A) = 0. deg-out(D) = 0, deg-in(D) = 2.
What to write in your book
- Directed network = edges have arrows showing one-way connections.
- In-degree = arrows pointing IN. Out-degree = arrows pointing OUT.
- Examples: one-way streets, Instagram follows, pipelines with pumps.
Worked examples · reveal each step
Five computers A, B, C, D, E are connected as follows: A connects to B and C; B connects to D; C connects to D and E; D connects to E. Draw this undirected network and find the degree of each vertex.
A directed network has edges: A→B, A→C, B→C, C→A, C→D. Find the in-degree and out-degree of each vertex.
A network has 4 vertices. Vertex P has a loop and connects to Q and R. Q connects to R. Is the network directed or undirected? Find deg(P).
- A network has vertices A, B, C, D with edges: A–B, A–C, B–C, B–D, C–D. Find the degree of each vertex.
- Explain why a loop at vertex X contributes 2 (not 1) to the degree of X.
- A social media site where you can follow people without them following you back: would this be modelled as directed or undirected? Justify.
- Draw a directed network with 3 vertices where every vertex has in-degree = 1 and out-degree = 1.
The "most connected" city is the one with the highest degree — the most edges meeting at that vertex. Sydney (degree 5) is most connected, followed by Liverpool (4), Parramatta (3), Penrith (2).
Measuring connectivity = counting the degree of each vertex. This simple idea — degree — is the foundation for all network algorithms you'll learn this module.
What has changed in your understanding? What surprised you?
Pick your answer, then rate your confidence.
Q1. Which term describes a point in a network that represents a city, person or location?
Q2. A vertex has edges connecting it to 3 other vertices and also has one loop. What is its degree?
Q3. A social media platform where A can follow B without B following A is best modelled as:
Q4. A vertex with degree 0 is called:
Q5. In a directed network, the number of arrows pointing INTO a vertex is called:
SA 1. A network has 5 vertices (A, B, C, D, E) with edges: A–B, A–C, A–D, B–C, D–E. (a) Find the degree of each vertex. (b) Verify your answer using the degree sum rule. (2 marks)
SA 2. Explain the difference between a directed and an undirected network. Give one real-world example of each. (2 marks)
SA 3. A network has degrees 4, 3, 3, 2, 2. (a) Is this degree sequence possible? (b) How many edges does the network have? (c) If one vertex has a loop, which vertex is it most likely to be, and why? (3 marks)
Comprehensive answers (click to reveal)
MC 1 — B: A vertex (node) is a point in the network representing a location, person or object.
MC 2 — C: 3 regular edges + loop (counts as 2) = 3 + 2 = 5.
MC 3 — A: Directed network — following is one-directional.
MC 4 — D: A vertex with no edges is isolated (degree 0).
MC 5 — B: In-degree counts arrows pointing INTO a vertex.
SA 1: (a) deg(A)=3, deg(B)=2, deg(C)=2, deg(D)=2, deg(E)=1. (b) Sum=10 = 2×5 edges ✓.
SA 2: Undirected: no direction, e.g. two-way roads. Directed: arrows, e.g. Twitter follows.
SA 3: (a) Sum = 14 (even) → possible. (b) 7 edges. (c) Vertex with degree 4 — a loop contributes 2, leaving 2 other connections.
Five timed questions on vertices, edges, degree and directed networks. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%).
⚔ Enter the arenaMark lesson as complete
Tick when you've finished the practice and review.