# Show that a graph with $n$ vertices and $n + 2$ edges must contain two edge-disjoint circuits.

Show that a graph with $$n$$ vertices and $$n + 2$$ edges must contain two edge-disjoint circuits.

I'm a bit confused by what an edge-disjoint circuit means here.

• "Edge-disjoint" means that you have two circuits with no edges in common. – Milo Brandt Nov 26 '18 at 18:36
• Hint: Use what you know about trees and the relationship between the number of edges and vertices in a tree. – JMoravitz Nov 26 '18 at 18:39
• Take $G = K_4$, which has 4 vertices and 6 edges, but for any circuit on three vertices, removing it leave a tree (which has no circuits), so this isn't true for $n=4$. – B. Mehta Nov 26 '18 at 19:23

Well but this isn't true though. Take $$K_4$$ and replace each edge by a path with $$k+1$$ vertices, where $$k$$ an arbitrarily large integer. This graph has $$4+6k$$ vertices and $$6+6k$$ edges.