# Induction, graphs and discrete reasoning

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

Course: [Abstract algebra and discrete proofs](https://studybrix.com/en/courses/algebra-and-discrete-proofs/index.md)
Level: university
Prerequisites: Logic and integer arithmetic.

## 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.

## Practice questions

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

Sample answer / 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.

Explanation: Credit both the base and valid induction step.

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

Answer: 15

Explanation: Each edge contributes two to the degree sum.

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

Answer: 11

Explanation: A finite tree has n−1 edges.

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

A. It equals the total number of edges
B. It is even
C. It is always zero
D. It is always odd

Answer: It is even

Explanation: 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 / marking guidance: The desired conclusion is used as a premise. The induction hypothesis must concern a previously established case, typically n.

Explanation: Credit identifying the unjustified assumption.

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

Answer: 32

Explanation: 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 / marking guidance: The remaining graph stays connected because the leaf was an endpoint only, and cannot gain a cycle by removal.

Explanation: Credit connectivity and acyclicity.

### 8. Does every connected graph have n−1 edges?

A. Only graphs with named vertices
B. Yes without exception
C. No graph can have that count
D. No; that count characterizes trees among connected finite graphs

Answer: No; that count characterizes trees among connected finite graphs

Explanation: Connected graphs can have cycles and extra edges.

## Further reading

- https://ocw.mit.edu/courses/18-100a-real-analysis-fall-2020/
- https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/

Original AI-assisted educational draft; not independently teacher-reviewed. References support further study, not copied exercises, affiliation or curriculum accreditation.