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

In summary, the conversation discusses the connectivity of a Hamiltonian-connected graph with at least 4 vertices. It is determined that the connectivity of the graph is at least 3, based on the existence of a Hamiltonian path between any two pairs of vertices and the fact that removing a pair of vertices would disconnect the graph.
  • #1
Solarmew
37
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
  • #2
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.
 
  • #3
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
 
  • #4
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?
 
  • #5
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...
 
  • #6
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?
 
  • #7
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:
  • #8
Yes, that's the argument.
 
  • #9
haruspex said:
Yes, that's the argument.

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

1. What is a Hamiltonian graph?

A Hamiltonian graph is a type of graph where a single path can be traced through all of its vertices, visiting each vertex exactly once.

2. How is connectivity of a graph determined?

The connectivity of a graph is determined by the minimum number of vertices that must be removed in order to disconnect the graph.

3. What does it mean for a graph to have a connectivity of 3?

A graph with a connectivity of 3 means that at least 3 vertices must be removed in order to disconnect the graph. This also means that there is at least one path that connects all remaining vertices in the graph.

4. Why does this proof specify n >= 4 vertices?

This proof specifies n >= 4 vertices because a graph with less than 4 vertices cannot have a connectivity of 3. This is because removing 3 vertices from a graph with only 3 vertices would result in a disconnected graph with 0 remaining vertices.

5. How is the proof for Hamiltonian graph connectivity done?

The proof for Hamiltonian graph connectivity is typically done by demonstrating that a graph with n >= 4 vertices and a connectivity of 3 can always be reduced to a simpler graph with n-1 vertices and a connectivity of 3. This process is repeated until a graph with only 3 vertices is reached, which cannot have a connectivity of 3. Therefore, it can be concluded that any graph with n >= 4 vertices must have a connectivity of 3.

Similar threads

MHB A Subset of a Graph with No Perfect Matching
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Minimum Degree of a Random Graph (Probabilistic Method)
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Prove the minimum and maximum edges in a graph
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
I The number of intersection graphs of ##n## convex sets in the plane
    • General Math
Replies
2
Views
689
MHB Graph Grammer Function For Two Exotic Graphs Question please.
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
MHB Graphs with N Nodes: Proving Cliques and Anti-Cliques
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
A Dressed states for a 3 level system
    • Atomic and Condensed Matter
Replies
6
Views
1K
MHB Proving the symmetry of self complementary graphs with n=4k+1
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Graph Theory. Decomposition of K_{2n+1} into hamiltonian cycles.
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
4K
MHB Probability of Having a Totally Dominating Set (Probabilistic Methods)
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K

Hot Threads

Recent Insights

Back
Top