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.
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.
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.
I got this idea from @B. Mehta 's comment.