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 a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...
Back
Top