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 onwhich 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.
A network has vertices (nodes) and edges (connections). Draw from a description by listing all vertices first, then adding each edge. An edge connects exactly two vertices (or loops back to the same vertex). Networks model any pairwise-connection system.
Pause, copy the two network definitions: vertex = a node or point; edge = a connection between exactly two vertices (or a loop back to itself), and the construction sequence (list all vertices first, then add each edge one by one) into your book.
We just saw that a network has vertices (nodes) and edges (connections), and that you draw it by listing all vertices first then adding each edge. That raises a question: once a network is drawn, what numerical property can we calculate for each vertex to describe how connected it is? This card answers it → the degree of a vertex is the number of edges meeting at that vertex; a loop counts as 2; and the degree sum theorem states that the sum of all degrees = 2 × number of edges (always even).
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.
Degree of a vertex = number of edges meeting at that vertex. A loop counts as 2 towards the degree of its vertex. Degree sum theorem: sum of all degrees = 2 × number of edges (always even). Odd-degree vertices always come in pairs.
Pause, copy the degree definition (number of edges at a vertex), the loop rule (a loop counts as 2 towards its vertex's degree), and the degree sum theorem (sum of all degrees = 2 × number of edges, always even) into your book.
We just saw degree of a vertex, the count of edges meeting at it, and the degree sum theorem: total degrees = 2 × edges. That raises a question: all edges so far allowed travel in both directions, what if the problem models a one-way street, a website link, or a flow that only goes one way? This card answers it → a directed network (digraph) has arrows on edges; each vertex has an in-degree (arrows arriving) and an out-degree (arrows leaving).
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.
Directed network (digraph): each edge has an arrow, travel is one-way. In-degree = number of arrows arriving; out-degree = number of arrows leaving. Total degree = in-degree + out-degree. Used to model one-way streets, web links, dependencies.
Pause, copy the directed network definition (edges have arrows, travel is one-way), the in-degree/out-degree distinction (in = arrows arriving; out = arrows leaving), and a real-world example (one-way streets, website links, water flow) into your book.
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.