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

286 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.