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.

  • $\begingroup$ "Edge-disjoint" means that you have two circuits with no edges in common. $\endgroup$ – Milo Brandt Nov 26 '18 at 18:36
  • $\begingroup$ Hint: Use what you know about trees and the relationship between the number of edges and vertices in a tree. $\endgroup$ – JMoravitz Nov 26 '18 at 18:39
  • 4
    $\begingroup$ 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$. $\endgroup$ – 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.

I got this idea from @B. Mehta 's comment.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.