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

1. 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.
2. Inductive hypothesis: Assume if every vertex has positive degree in a graph on $k$ vertices, then the graph is connected.
3. 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.

It turns out that 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$. $a \mod m$ is congruent to one integer in the set $\{0, 1, \cdots, m-1\}$.

If $a \equiv c \mod m$ and $b \equiv d \mod m$ then $a+b \equiv c+d \mod m$ and $a b \equiv c d \mod m$. Subsequently, $a^k \equiv c^k \mod m$.

$a$ and $b$ are multiplicative inverses modulo $m$ when $a b \equiv 1 \mod m$. $a$ has a multiplicative inverse if and only if $\gcd(a, m) = 1$.