# Induction on simple graphs

• Jan 13th 2013, 07:15 AM
MachinePL1993
Induction on simple graphs
Hello,

We say that a simple graph $G=\langle V,E \rangle$ is connected, when the transitive and reflexive closure of relation $E$ is equal to $V \times V$ (which basically means that we can find a route to any two vertices of a graph). Show through induction that for any $n \in \mathbb{N}$ every simple connected graph with $n$ vertices has at least $n-1$ edges.

Well the base step is easy, since when we are dealing with one vertex the relations reflexive closure is equal to the cartesian product $V \times V$.

Then I suppose we assume that a simple, connected graphs with $n$ vertices has at least $n-1$ edges. That we take any simple, connected graph with $n+1$ vertices, but I am a a loss as to how get from the assumption we made for graph with $n$ vertices to proving it also works for $n+1$ vertices.

Edit:

Please tell me if I'm even remotely right with this.

First we have to see, that any connected graph has at least two vertices, which if we "cut" the graph will remain connected.
PROOF:
Let $d(u,v)$ be the lenght of the shortest road between two vertices. Since we have a finite number of vertices and edges, we can find $x , y$ such that $d(x,y)$ is the biggest. Than let's assume indirectly that when we cut $x$ that graph will become disconnected. Let's take any $z$ that was connected to $y$ before $x$ was cut and now isn't. That the road $d(z,y)=d(z,x)+d(x,y)>d(x,y)$ which goes against our assumption that $d(x,y)$ was the largest possible road. We have a contradiction, which means that when we cut $x$ the graph remains connected. Same goes for $y$.

Now let's look at our connected, simple graph with $n+1$ vertices. Let's "delete" from it the $v$ that is a non cut vertex. Than we have a connected graph with $n$ vertices, which by inductive assessment has at least $n-1$ edges. Since the deleted $v$ has to connect to at least one other vertex to be in relation with other vertices we have that for a connected graph with $n+1$ vertices it has at least $n-1+1=n$ edges.