What would you like to understand?

Popular destinationsCalculatorsCoursesPracticeFormulas

Unlock Premium Help

Explore every tutor and study workspace for seven days, with no daily AI cap during the trial.

Choose a billing period
Ask a parent to pay

Nothing is charged during the first seven days. Unless you cancel, the plan you selected begins when the trial ends and renews on its stated schedule. Manage cancellation from your plan page. Stripe handles the payment details.

Handshaking lemma formula: what it means and how to use it

Relate all vertex degrees to the number of edges in an undirected graph. This graphs relationship belongs to discrete math. Read the symbols against the problem, confirm the required conditions, and estimate the scale before calculating.

\[\sum_{v\in V}\deg(v)=2|E|\]

Read the objects and logical claim in Handshaking lemma

Identify the set, index, graph, counting object, or proposition first. Then separate what is assumed from what is being counted or proved. Rebuild missing background in the discrete math subject guide, then use discrete math practice to retrieve the relationship without being told its name.

State the finite, integer, or logical conditions

It is a statement about undirected graphs. In a directed graph each arrow adds 1 to one vertex's out-degree and 1 to another's in-degree, so you count those two totals separately and each equals the number of arrows on its own.

Test Handshaking lemma on a small case

List or draw a small instance before relying on the general notation:

\[A graph with $7$ edges has total degree $14$.\]

Extend the small case to the general structure

  1. Name the unknown, and the unit the answer has to come out in.
  2. Match the symbols to your values. $V$ is vertex set and $E$ edge set.
  3. Check the conditions before substituting. Each undirected edge contributes two degree incidences; loops require the usual degree-two convention.
  4. Substitute, keep exact values to the last line, then test the sign, size, and unit against a rough estimate - The check that catches most discrete math slips.

Check boundaries, overlap, and base cases

After using Handshaking lemma, repeat the calculation with units attached and test the result against a boundary case or a quick numerical estimate.

A counting or logic mistake to catch

What goes wrong: Students treat the total degree as the number of edges and forget to halve it.

Why it fails: Each edge was counted from both ends, so the total degree always overstates the edge count by a factor of exactly two.

Repair: Divide the degree total by 2. If six people each shake hands with three others, the degrees add to 18, so there were 9 handshakes, not 18.

Questions about Handshaking lemma

Can a graph have exactly three vertices of odd degree?

No. The degree total must be even, and odd degrees can only pair up to an even total in even numbers, so the count of odd-degree vertices is always even. This is the lemma's most useful corollary.

How does a loop count toward degree?

It counts 2, because both of its ends attach to the same vertex. That convention exists precisely so the lemma keeps working when loops are allowed.

Why is it called the handshaking lemma?

Picture people as vertices and handshakes as edges. Adding up how many hands each person shook double counts every handshake, since two people take part in each one.

What is the total degree of a graph with 7 edges?

Exactly 14, whatever the shape. That works in reverse too: if the degrees you listed add to an odd number, you have miscounted somewhere.

Make it yours

Change one input, predict whether the output should rise, fall, or stay fixed, and only then recalculate.