Results 1 to 3 of 3

Math Help - graph theory

  1. #1
    Junior Member
    Joined
    Jan 2009
    Posts
    32

    Exclamation graph theory

    prove that for any simple, connected graph G, if G has exactly one cycle, then G has the same number of nodes and edges

    the hints are to use exercise 2 and theorem 7.

    exercise 2 is a proof of "when an edge is removed from a cycle in a connected graph, the result is a graph that is still connected."

    and theorem 7 is "if T is a tree with n edges, then T has n+1 vertices"

    i'm completely lost, any ideas would be greatly appreciated
    thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by mathh18 View Post
    prove that for any simple, connected graph G, if G has exactly one cycle, then G has the same number of nodes and edges the hints are to use exercise 2 and theorem 7.
    exercise 2 is a proof of "when an edge is removed from a cycle in a connected graph, the result is a graph that is still connected."
    and theorem 7 is "if T is a tree with n edges, then T has n+1 vertices"
    Here are some hints.
    This graph has exactly one cycle.
    A tree is a connected acyclic graph.
    If you remove one edge in the cycle the graph is connected with n-1 edges.
    How can you use theorem 7?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2009
    Posts
    32
    do i use induction? i'm confused..
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 05:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum