How to Prove the Existence of a Cycle Subgraph for k-Connected Graphs?

  • Thread starter Thread starter andreass
  • Start date Start date
  • Tags Tags
    Graph
AI Thread Summary
For every k-connected graph with at least 2*k vertices, a cycle subgraph with at least 2*k vertices exists, which is evident for k=2. The challenge arises in proving this for k>2, as the initial poster seeks hints for a proof. The definition of k-connectedness is confirmed, with an alternative definition provided that emphasizes the existence of k internally disjoint paths between any two vertices. The discussion highlights the need for a deeper exploration of graph theory concepts to establish the proof for higher values of k. Understanding these definitions and properties is crucial for advancing the proof.
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
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top