Results 1 to 1 of 1

Thread: Induction on simple graphs

  1. #1
    Junior Member
    Nov 2012

    Induction on simple graphs


    We say that a simple graph $\displaystyle G=\langle V,E \rangle$ is connected, when the transitive and reflexive closure of relation $\displaystyle E$ is equal to $\displaystyle 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 $\displaystyle n \in \mathbb{N}$ every simple connected graph with $\displaystyle n$ vertices has at least $\displaystyle 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 $\displaystyle V \times V$.

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


    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.
    Let $\displaystyle 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 $\displaystyle x , y$ such that $\displaystyle d(x,y)$ is the biggest. Than let's assume indirectly that when we cut $\displaystyle x$ that graph will become disconnected. Let's take any $\displaystyle z$ that was connected to $\displaystyle y$ before $\displaystyle x$ was cut and now isn't. That the road $\displaystyle d(z,y)=d(z,x)+d(x,y)>d(x,y)$ which goes against our assumption that $\displaystyle d(x,y)$ was the largest possible road. We have a contradiction, which means that when we cut $\displaystyle x$ the graph remains connected. Same goes for $\displaystyle y$.

    Now let's look at our connected, simple graph with $\displaystyle n+1$ vertices. Let's "delete" from it the $\displaystyle v$ that is a non cut vertex. Than we have a connected graph with $\displaystyle n$ vertices, which by inductive assessment has at least $\displaystyle n-1$ edges. Since the deleted $\displaystyle 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 $\displaystyle n+1$ vertices it has at least $\displaystyle n-1+1=n$ edges.
    Last edited by MachinePL1993; Jan 13th 2013 at 07:51 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Dual, k-connected, plane and simple graphs.
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 1st 2010, 10:21 AM
  2. Replies: 5
    Last Post: Aug 10th 2010, 02:00 AM
  3. Induction on Connected Graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 25th 2010, 12:37 PM
  4. Simple Graphs and Paths
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2009, 09:10 AM
  5. Simple induction help
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: Sep 29th 2008, 06:29 AM

Search Tags

/mathhelpforum @mathhelpforum