Results 1 to 2 of 2

Math Help - Induction on Connected Graphs

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    2

    Induction on Connected Graphs

    If anyone could give any suggestions or help me solve this it would be greatly appreciated!

    Problem Use induction to prove the following theorem. For the purposes of this question, a graph is a finite set of points in the plane, some of which are connected by straight line segments, none of which intersect. A
    graph is connected if you can get from any point of the graph to any other by going on the line segments.

    Theorem. Suppose G is a connected graph. Then
    vG + rG = eG + 2 (1)
    where
     vG is the number of points.
     rG is the number of regions (counting the in nite outside area as one region).
     eG is the number of line segments.

    The proof may use any of the following facts:
    Fact. If G is any connected graph, then at least one of the following is true:
    1. G has only one point (and so has no lines and one region).
    2. G has at least one edge with one free end, so that removing that edge and the free point will still leave
    a connected graph (with the same regions as before).
    3. G has an edge which can be deleted, without removing any points, leaving a connected graph and merging
    two regions of the original graph into one region.


    Thanks again.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by geometrywiz View Post
    If anyone could give any suggestions or help me solve this it would be greatly appreciated!

    Problem Use induction to prove the following theorem. For the purposes of this question, a graph is a finite set of points in the plane, some of which are connected by straight line segments, none of which intersect. A
    graph is connected if you can get from any point of the graph to any other by going on the line segments.

    Theorem. Suppose G is a connected graph. Then
    vG + rG = eG + 2 (1)
    where
     vG is the number of points.
     rG is the number of regions (counting the in nite outside area as one region).
     eG is the number of line segments.
    That is Euler's Formula for faces & edges of a planar graph.
    That webpage has a complete disscussion.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Connected Graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 10th 2011, 02:04 AM
  2. Table of Connected Graphs
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 20th 2010, 06:40 PM
  3. Isomorphic Connected Graphs
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: April 12th 2010, 05:37 PM
  4. Connected Hausdorff spaces and graphs
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: March 12th 2010, 10:51 AM
  5. Strongly connected graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 17th 2008, 12:18 PM

Search Tags


/mathhelpforum @mathhelpforum