# G has at least one cycle or exactly one cycle?

Consider a simple connected graph $G$ with n vertices and n edges $(n>2)$. Then, which of the following statements are true?

1. $G$ has no cycles
2. The graph obtained by removing any edge from $G$ is not connected
3. $G$ has at least one cycle
4. The graph obtained by removing any two edges from $G$ is not connected

My attempt :

1. always false
2. not always true
3. true (since exactly one is subset of at least one !).
4. always true

Can you explain in formal way, please?

• I think you are right: Option 3 is always correct. And no, it may not be an Euler graph. Consider a tree where every node is connected to a unique root, and add one more edge. Sep 10 '15 at 11:02
• The third option is correct, otherwise you would deal with a forset ( a disjoint union of trees). But a standard exercize shows that in a tree $|V|-|E|=1$, so you cannot have the same number of edges and vertices. Sep 10 '15 at 11:03
• Yes , here given graph is connected . I'm able to find the exactly one cycle such given graph . So , on basis only "exactly one is subset of at least one" , option 3 is true , but there is no graph such that contain cycle more than exactly one ! Am I right ? or that graphs are exists ? Sep 10 '15 at 12:03
• It is exactly one, as you say. One way to see it is to suppose that by adding an $n$-th edge to a graph with $n - 1$ edges, you get two cycles (which couldn't have been there before). Then the two cycles share the inserted edge, and you should then be able to see a cycle that doesn't contain this edge. Sep 10 '15 at 21:16
• @ManuelLafond , as you "by adding an n-th edge to a graph with n−1 edges, you get two cycles" , how ? Is order of cycle matter here ? Sep 11 '15 at 5:49

1) Always false. A graph with no cycles (also known as a tree) has $n$ nodes and $n-1$ edges. Add one more edge and you're going to make a cycle somewhere. You can prove this by induction.
2) Not necessarily true. Easy counterexample: a graph with $n$ nodes and $n$ edges that forms a circle (i.e. a single cycle). Take out an edge anywhere and the graph is still connected.
4) Always true. Think about it like this: if it's a connected graph with $n$ vertices and $n$ edges, and you remove one edge, then you have $n-1$ edges. If it's still connected, then it's a tree. (If it is not connected, then we're done.) Now you have a tree. Remove any edge from a tree, and your tree is split into two connected components.