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

  • Context: Graduate 
  • Thread starter Thread starter andreass
  • Start date Start date
  • Tags Tags
    Graph
Click For Summary
SUMMARY

For every k-connected graph with k ≥ 2 and at least 2*k vertices, there exists a subgraph that is a cycle containing at least 2*k vertices. This conclusion is straightforward for k=2, where the cycle can be visualized with or without additional edges. The discussion also clarifies the definition of k-connected graphs, emphasizing that a graph is k-connected if it contains k internally disjoint paths between any two vertices. The challenge lies in proving this for k > 2.

PREREQUISITES
  • Understanding of k-connected graphs
  • Familiarity with graph theory concepts
  • Knowledge of subgraph properties
  • Ability to analyze vertex connectivity
NEXT STEPS
  • Study the properties of k-connected graphs in detail
  • Research proofs related to cycle existence in graph theory
  • Explore the concept of internally disjoint paths in graph connectivity
  • Investigate examples of k-connected graphs for practical understanding
USEFUL FOR

Mathematicians, computer scientists, and students studying graph theory, particularly those interested in connectivity and cycle properties in graphs.

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
 

Similar threads

  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 6 ·
Replies
6
Views
3K
  • · Replies 15 ·
Replies
15
Views
5K
  • · Replies 29 ·
Replies
29
Views
6K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
4
Views
4K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 7 ·
Replies
7
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
3K