Skip to main content
MathidiaMathematics Academy
Discrete mathematics
Lesson 61 of 75
Introduction

Graphs and networks

Objective. Use vertices, edges, degree and connectivity accurately.

  1. 1. Learn
  2. 2. Worked example
  3. 3. Practice
  4. 4. Feedback
  5. 5. Continue

Learn: the key idea

In discrete mathematics, a graph consists of vertices (nodes) connected by edges, and the language used to describe graphs includes terms such as degree (the number of edges at a vertex), a walk, path or cycle (sequences of edges with varying restrictions on repetition), and whether a graph is connected (every vertex reachable from every other) or a tree (connected with no cycles). A simple graph has no loops or multiple edges between the same pair of vertices. For example, a tree with n vertices always has exactly n−1 edges, a key structural fact used throughout discrete mathematics.

Worked example

A connected graph has 8 vertices and is a tree. State the number of edges, and explain which property of trees justifies your answer.

8
Coordinate grid with the line 8
  1. 1A tree is defined as a connected graph with no cycles
  2. 2A key property of trees is that they have exactly one fewer edge than the number of vertices
  3. 3With 8 vertices, the number of edges is 8 − 1
  4. 4This gives 7 edges, since any additional edge would create a cycle, and any fewer would disconnect the graph

Answer: 7 edges

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. Students confuse a 'path' (no repeated vertices) with a 'walk' (vertices and edges may repeat), leading to incorrect counts or claims about connectivity. Always check the precise definition being used: walk, trail, path or cycle each have distinct meanings.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard