Graph Theory

Bridges of Königsberg

Graph theory began in 1736 when Leonard Euler (1707-1783) solved the problem of the Bridges of Königsberg.

The question was to find a walking path, leaving and arriving home, that goes through the seven bridges of Königsberg, laid as follow:

████████████████████████████████
██░░░░░░░║░░░░░║░░░░░░░░░║░░░░░░░░░
░░░░░░████████████════███████░░░░░░
██░░░░░░║░░░░║░░░░░░░░░░║░░░░░░░░░
████████████████████████████████

To Prove that there is no such path, he discarded the unnecessary issues of the problem. He realized that this was a connection problem. As such it could be represented as:

flowchart LR

 N[North] 
 I1[Island1]
 I2[Island2]
 S[South]

 N---I1
 N---I1
 N---I2
 I1---I2
 S---I1
 S---I1
 S---I2

This is a graph with four vertices (the territories).

---

To prove by mathematical induction that a complete graph on $( n )$ points has exactly $( \frac{n(n - 1)}{2} )$ lines (or edges), let's go through the steps.

Understanding the Problem

A complete graph on $( n )$ points, denoted $( K_n )$, is a graph in which every point (or vertex) is connected to every other point by a unique line (or edge). The goal is to show that the number of lines in $( K_n )$ is given by:

\text{Number of lines in } K_n = \frac{n(n - 1)}{2}.

Step 1: Base Case

We start by verifying the formula for $( n = 1 )$ and $( n = 2 )$.

1. For $( n = 1 )$:
   • A complete graph on 1 point, $( K_1 )$, has no other points to connect to, so there are $( 0 )$ lines.
   • The formula gives:

\frac{1 \cdot (1 - 1)}{2} = \frac{1 \cdot 0}{2} = 0.

• This matches the actual count, so the formula holds for $( n = 1 )$.

2. For $( n = 2 )$:
   • A complete graph on 2 points, $( K_2 )$, has exactly 1 line connecting the two points.
   • The formula gives:

\frac{2 \cdot (2 - 1)}{2} = \frac{2 \cdot 1}{2} = 1.

• This matches the actual count, so the formula holds for $( n = 2 )$.

Thus, the base case is true for $( n = 1 )$ and $( n = 2 )$.

Step 2: Inductive Hypothesis

Assume that the formula holds for some positive integer $( k )$; that is, assume:

\text{Number of lines in } K_k = \frac{k(k - 1)}{2}.

This assumption is called the inductive hypothesis.

Step 3: Inductive Step

We need to prove that if the formula holds for $( K_k )$, then it also holds for $( K_{k+1} )$. In other words, we need to show:

\text{Number of lines in } K_{k+1} = \frac{(k + 1)k}{2}.

Proof of the Inductive Step

1. Adding a New Point:

   • Consider a complete graph $( K_{k+1} )$ with $( k + 1 )$ points.
   • We can think of this graph as starting with $( K_k )$ (a complete graph on $( k )$ points) and then adding a new point $( P_{k+1} )$.
   • This new point $( P_{k+1} )$ must connect to each of the $( k )$ existing points in $( K_k )$.

2. Count the New Lines:

   • By adding $( P_{k+1} )$, we create exactly $( k )$ new lines, one connecting $( P_{k+1} )$ to each of the $( k )$ existing points.
   • So, the total number of lines in $( K_{k+1} )$ is the number of lines in $( K_k )$ plus these $( k )$ new lines:

     \text{Number of lines in } K_{k+1} = \frac{k(k - 1)}{2} + k.
     ```

3. **Simplify the Expression**:
   - Now, let’s simplify $( \frac{k(k - 1)}{2} + k )$:
```math
     \frac{k(k - 1)}{2} + k = \frac{k(k - 1) + 2k}{2} = \frac{k^2 - k + 2k}{2} = \frac{k^2 + k}{2}.
     ```
   - We can factor out $( k + 1 )$ in the numerator:
```math
     \frac{k^2 + k}{2} = \frac{k(k + 1)}{2}.
     ```

This matches the formula we set out to prove for $( n = k + 1 )$:
```math
\text{Number of lines in } K_{k+1} = \frac{(k + 1)k}{2}.

Conclusion

Since we have shown that:

1. The formula holds for the base cases $( n = 1 )$ and $( n = 2 )$,
2. If the formula holds for $( n = k )$, then it also holds for $( n = k + 1 )$,

we conclude by the principle of mathematical induction that the formula is true for all positive integers $( n )$:

\boxed{\text{Number of lines in } K_n = \frac{n(n - 1)}{2}}.