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

  1. Base case: If we have vertex then the proposition is vacuously true. If we have vertices with no edge then the proposition is vacuously true; with one edge between the two vertices, each edge has degree (positive) and the graph is connected.
  2. Inductive hypothesis: Assume if every vertex has positive degree in a graph on vertices, then the graph is connected.
  3. Inductive step: Begin with a graph on 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 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 vertices with positive degree is connected.

Since we proved a graph with vertices with positive degree that is connected can create a graph with 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 in the inductive step, we incorrectly assume that the proof applies for every graph on vertices with positive degree. We only show that it’s true for some graphs on vertices: only the ones that can be built up from graphs on vertices that are already connected. To avoid build-up error in proofs, begin with vertices/edges and remove one, so you can use the inductive hypothesis for vertices/edges.

Modular Arithmetic

If (pronounced “ is congruent to modulo ”) then for some integer . is congruent to one integer in the set .

If and then and . Subsequently, .

and are multiplicative inverses modulo when . has a multiplicative inverse if and only if .