Skip to main content
MathidiaMathematics Academy
Discrete mathematics
Lesson 48 of 75
Standard practice

Graphs and degree

Objective. Use paths, connectivity and the handshaking lemma.

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

Learn: the key idea

A graph is a mathematical structure consisting of vertices connected by edges, used to model networks such as social connections or road systems, and the degree of a vertex is the number of edges incident to it. A path is a sequence of distinct vertices each connected by an edge to the next, and a graph is connected if a path exists between every pair of vertices. The handshaking lemma states that the sum of all vertex degrees equals twice the number of edges, Σdeg(v) = 2|E|, because each edge contributes exactly 1 to the degree count of its two endpoints. This immediately implies that the number of vertices with odd degree must always be even, since an odd total would be impossible from a sum that is always a multiple of 2.

Worked example

A graph has vertices with degrees 3, 3, 2, 2. Use the handshaking lemma to find the number of edges in this graph.

3 … 3
Coordinate grid with the line 3 … 3
  1. 1Recall the handshaking lemma: Σdeg(v) = 2|E|.
  2. 2Sum the given degrees: 3 + 3 + 2 + 2 = 10.
  3. 3Set this sum equal to twice the number of edges: 10 = 2|E|.
  4. 4Divide both sides by 2 to find the number of edges.

Answer: 5 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 sum the degrees of all vertices and treat that total as the number of edges directly; the handshaking lemma requires dividing this sum by 2, since each edge is counted at both of its endpoints.

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