Proving Hamiltonian Graph Connectivity is 3: n >= 4 Vertices

  • Context: Graduate 
  • Thread starter Thread starter Solarmew
  • Start date Start date
  • Tags Tags
    Graph Hamiltonian
Click For Summary

Discussion Overview

The discussion revolves around proving that the connectivity of a Hamiltonian-connected graph (HC graph) with at least 4 vertices is at least 3. Participants explore various approaches to establish this claim, focusing on concepts of vertex connectivity and Hamiltonian paths.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant suggests starting with the number of unique Hamiltonian paths in a graph with 4 vertices, indicating a combinatorial approach.
  • Another participant proposes examining a cutset of two edges to explore conditions under which a Hamiltonian path can exist between two vertices.
  • There is a clarification that the focus is on vertex connectivity rather than edge connectivity, with an assertion that the smallest vertex cut is 3.
  • Participants discuss the implications of removing two vertices and the resulting disconnection of the graph, questioning the existence of a Hamiltonian path between the remaining vertices.
  • One participant reflects on the contradiction that arises when assuming a Hamiltonian path exists between two vertices whose removal disconnects the graph, leading to a deeper exploration of the argument.
  • Another participant acknowledges their initial misunderstanding and attempts to articulate the reasoning behind the proof, emphasizing the necessity of paths connecting components of the graph.
  • Several participants express uncertainty about their explanations and seek to refine their proof language.

Areas of Agreement / Disagreement

Participants generally agree on the need to prove that the connectivity is at least 3, but there are varying interpretations and approaches to the argument, leading to some confusion and refinement of ideas.

Contextual Notes

Participants express uncertainty about the clarity of their arguments and the proof structure, indicating that the discussion is still in a formative stage with unresolved aspects.

Who May Find This Useful

Readers interested in graph theory, particularly those studying Hamiltonian graphs and connectivity concepts, may find this discussion relevant.

Solarmew
Messages
37
Reaction score
1
Suppose G is a HC (Hamiltonian-connected) graph on n >= 4 vertices. Show that connectivity of G is 3.
I tried starting by saying that there would be at least 4C2=6 unique hamiltonian paths. But then I'm not sure where to go from here.
Any hints would be appreciated.
 
Physics news on Phys.org
I assume this is edge connectivity.
Suppose there's a cutset of two edges. In relation to these edges, find two points for which there can only be a Hamiltonian path between them under very restrictive conditions.
 
haruspex said:
I assume this is edge connectivity.
Suppose there's a cutset of two edges. In relation to these edges, find two points for which there can only be a Hamiltonian path between them under very restrictive conditions.

it's vertex connectivity, sorry >.> so the smallest number of vertices in any vertex cut of G is 3
 
Solarmew said:
it's vertex connectivity, sorry >.> so the smallest number of vertices in any vertex cut of G is 3
OK, same deal, only easier. You're trying to prove connectivity >= 3. So assume false. That means there's a pair vertices whose removal would leave a disconnected graph. Is there a Hamiltonian path between them?
 
haruspex said:
OK, same deal, only easier. You're trying to prove connectivity >= 3. So assume false. That means there's a pair vertices whose removal would leave a disconnected graph. Is there a Hamiltonian path between them?

There is. Since G is HC, there's a Hamiltonian Path b/w every two pairs of vertices.
But I'm not sure how there being a path is helpful >.>
hm, let me think about that for a sec...
 
Solarmew said:
There is. Since G is HC, there's a Hamiltonian Path b/w every two pairs of vertices.
But I'm not sure how there being a path is helpful >.>
hm, let me think about that for a sec...
No, I mean take any graph that has a pair of vertices whose removal would render the graph disconnected. Draw a diagram. How could it have a Hamiltonian path between those two vertices?
 
ooooh, there isn't a HP b/w them, i lied ... i was just testing you XD ... by doodling it out i can kinda see it i think +.+ but I'm not sure how to put it in words ...
like if by removing those two vertices (let's say u,v) we disconnected the graph, that would mean that the only paths from one component to the other were through u and v. But that would mean that if we tried to find a Hamiltonian path from u to v we would not be able to go from one block of G to the other without passing through v, so we would only be able to go through the vertices of one block of G before inevitably ending up at v.
gah ... that doesn't sound very convincing >.< ... i need to work on my proof speak :<
 
Last edited:
Yes, that's the argument.
 
haruspex said:
Yes, that's the argument.

= ^.^ = thanks, i appreciate your help!
 

Similar threads

MHB Is HSC NP-Complete in Graph Theory?
  • · Replies 1 ·
Replies
1
Views
2K
MHB A Subset of a Graph with No Perfect Matching
  • · Replies 1 ·
Replies
1
Views
2K
MHB Minimum Degree of a Random Graph (Probabilistic Method)
  • · Replies 1 ·
Replies
1
Views
2K
MHB Graph Grammer Function For Two Exotic Graphs Question please.
  • · Replies 4 ·
Replies
4
Views
2K
MHB Graphs with N Nodes: Proving Cliques and Anti-Cliques
  • · Replies 6 ·
Replies
6
Views
3K
MHB Graph Theory. Decomposition of K_{2n+1} into hamiltonian cycles.
  • · Replies 2 ·
Replies
2
Views
5K
MHB Some basic questions on Graph theory
  • · Replies 2 ·
Replies
2
Views
2K
MHB Prove the minimum and maximum edges in a graph
  • · Replies 6 ·
Replies
6
Views
2K
Undergrad The number of intersection graphs of ##n## convex sets in the plane
  • · Replies 2 ·
Replies
2
Views
1K
MHB Another tree-related graph theory proof
  • · Replies 1 ·
Replies
1
Views
2K