Thread: Induction on simple graphs

Hello,

We say that a simple graph is connected, when the transitive and reflexive closure of relation is equal to (which basically means that we can find a route to any two vertices of a graph). Show through induction that for any every simple connected graph with vertices has at least 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 .

Then I suppose we assume that a simple, connected graphs with vertices has at least edges. That we take any simple, connected graph with vertices, but I am a a loss as to how get from the assumption we made for graph with vertices to proving it also works for 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 be the lenght of the shortest road between two vertices. Since we have a finite number of vertices and edges, we can find such that is the biggest. Than let's assume indirectly that when we cut that graph will become disconnected. Let's take any that was connected to before was cut and now isn't. That the road which goes against our assumption that was the largest possible road. We have a contradiction, which means that when we cut the graph remains connected. Same goes for .

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