StudyBrixFree worksheets, study guides and courses

Mathematics · University

Induction, graphs and discrete reasoning

Prove a base case and a step from n to n+1; neither alone suffices.

Make a worksheet

Prerequisites

Logic and integer arithmetic.

Study notes

Induction

Prove a base case and a step from n to n+1; neither alone suffices.

Graph degrees

In a finite undirected graph, the sum of vertex degrees is twice the number of edges.

Trees

A finite connected acyclic graph with n vertices has n−1 edges.

Proof versus pattern

A pattern in numerical examples suggests a conjecture but does not prove it.

Worked examples

Prove 1+2+...+n=n(n+1)/2 by induction for n≥1.

Credit both the base and valid induction step.

The base n=1 holds. Assuming the formula for n, add n+1 to get n(n+1)/2+(n+1)=(n+1)(n+2)/2.

A finite undirected graph has degree sum 30. How many edges does it have?

Each edge contributes two to the degree sum.

15

Check your understanding

  1. A tree has 12 vertices. How many edges does it have?

  2. What must be true of the number of odd-degree vertices in a finite undirected graph?

    1. It equals the total number of edges
    2. It is even
    3. It is always zero
    4. It is always odd

  3. Why is assuming the statement for n+1 while proving it for n+1 circular?

  4. How many subsets does a 5-element set have?

Answers and marking guidance

Answers and marking notes
  1. 11

    A finite tree has n−1 edges.

  2. It is even

    The degree sum is even, so the sum of odd contributions contains an even number of odd terms.

  3. The desired conclusion is used as a premise. The induction hypothesis must concern a previously established case, typically n.

    Credit identifying the unjustified assumption.

  4. 32

    Each element is independently included or excluded, giving 2^5.

Further reading and review references

These are reference links, not copied exercises, institutional endorsement or proof of independent review.

AI-assisted preview; independent educational review required. Level labels describe prerequisites, not accreditation or official curriculum alignment.