Discussion 3A

Build-up Error in Graphs

Prove that if every vertex in a graph has positive degree, then the graph is connected.

Proof: Induction on the number of vertices

n

Base case: If we have $n=1$ vertex then the proposition is vacuously true. If we have $n=2$ vertices with no edge then the proposition is vacuously true; with one edge between the two vertices, each edge has degree $1$ (positive) and the graph is connected.

Inductive hypothesis: Assume if every vertex has positive degree in a graph on $k$ vertices, then the graph is connected.

Inductive step: Begin with a graph on $k$ vertices where every vertex has positive degree. The inductive hypothesis says this graph is connected. Then adding a new vertex with positive degree gives us a graph with $k+1$ vertices, all with positive degree. Since the new vertex has positive degree, it has some edge connecting it to another vertex in the original graph, meaning the graph with $k+1$ vertices with positive degree is connected.

Since we proved a graph with

k

vertices with positive degree that is connected can create a graph with

k+1

vertices with positive degree that is connected, the proof is complete.

This is actually a false statement, which can be disproved with the counterexample consisting of two disjoint edges on four vertices.

The issue is that in showing

P(k) \Rightarrow P(k+1)

in the inductive step, we incorrectly assume that the proof applies for every graph on

k+1

vertices with positive degree. We only show that it’s true for some graphs on

k+1

vertices: only the ones that can be built up from graphs on

k

vertices that are already connected.

To avoid build-up error in proofs, begin with

k+1

vertices/edges and remove one, so you can use the inductive hypothesis for

k

vertices/edges.

Modular Arithmetic

If $a \equiv b \mod m$ (pronounced “ $a$ is congruent to $b$ modulo $m$ ”) then $a = b + m k$ for some integer $k$ .