Thread: 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!

Originally Posted by mathh18

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 edges.
How can you use theorem 7?

do i use induction? i'm confused..