StudyBrixFree worksheets, study guides and courses

Mathematics · lesson 3 of 3

Induction, graphs and discrete reasoning

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

University8 practice questionsNotes + worked examples
Take the quizStudy guideRevision sheet

Learn the ideas

Prerequisites: Logic and integer arithmetic.

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

Example 1

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.

Example 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

8 questions

Decimals or fractions are accepted for numeric answers. Proofs and written responses use sample answers and require human marking. This is practice, not a protected examination.

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

Sample answer and marking guidance

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.

Credit both the base and valid induction step.

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

Show answer and explanation

15

Each edge contributes two to the degree sum.

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

Show answer and explanation

11

A finite tree has n−1 edges.

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

Show answer and explanation

It is even

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

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

Sample answer and marking guidance

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

Credit identifying the unjustified assumption.

6 How many subsets does a 5-element set have?

Show answer and explanation

32

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

7 Explain why removing a leaf and its edge from a tree leaves a smaller tree.

Sample answer and marking guidance

The remaining graph stays connected because the leaf was an endpoint only, and cannot gain a cycle by removal.

Credit connectivity and acyclicity.

8 Does every connected graph have n−1 edges?

Show answer and explanation

No; that count characterizes trees among connected finite graphs

Connected graphs can have cycles and extra edges.

Further reading and review references

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