Proving k-connected graphs contain cycles with at least 2k vertices

  • Level: Graduate 
  • Thread starter Thread starter andreass
  • Start date Start date
  • Tags Tags
    Graph
Join the discussion
Registration is free. Start your own thread to ask a follow-up.
2 replies · 4K views
andreass
Messages
14
Reaction score
0
How to prove that for every k-connected graph (k>=2) with at least 2*k vertices, there exists subgraph, which is cycle with at least 2*k vertices?
Ok, it’s obvious for k=2. It looks something like cycle with or without some other edges:
path3906.png


But I've no ideas how to prove it for k>2
Any hints?
 
Physics news on Phys.org
Yes, it's the same.
But in my opinion "better" definition is:
Graph is k-connected if and only if it contains k internally disjoint paths between any two vertices