Mixing
Is this graph Hamiltonian and how to prove it is not? [closed]
2
$begingroup$
How to prove this graph is not Hamiltonian (does not contain a Hamiltonian cycle)?
I have already tried removing some vertices from the graph, but I cannot get more than 7 connected components after 7 removed vertices.
Another way was to try to prove it by contradiction, and to assume it has Hamiltonian cycle. The problem is it seems too complex and I have no idea how to try and contradict it.
The actual question was to check if this graph is Hamiltonian, and if yes to draw the cycle, if not to prove it is not Hamiltonian. It is obvious that there is no Hamiltonian cycle, but how to prove it, because removing vertices does not work?
Thanks!
graph-theory hamiltonian-path
asked Jan 23 at 21:20
HarisHaris
263
$endgroup$
closed as off-topic by Gregory J. Puleo, Adrian Keister, Paul Frost, Cesareo, clathratus Jan 24 at 3:30
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Gregory J. Puleo, Adrian Keister, Paul Frost, Cesareo, clathratus
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
2
$begingroup$
How to prove this graph is not Hamiltonian (does not contain a Hamiltonian cycle)?
I have already tried removing some vertices from the graph, but I cannot get more than 7 connected components after 7 removed vertices.
Another way was to try to prove it by contradiction, and to assume it has Hamiltonian cycle. The problem is it seems too complex and I have no idea how to try and contradict it.
The actual question was to check if this graph is Hamiltonian, and if yes to draw the cycle, if not to prove it is not Hamiltonian. It is obvious that there is no Hamiltonian cycle, but how to prove it, because removing vertices does not work?
Thanks!
graph-theory hamiltonian-path
asked Jan 23 at 21:20
HarisHaris
263
$endgroup$
closed as off-topic by Gregory J. Puleo, Adrian Keister, Paul Frost, Cesareo, clathratus Jan 24 at 3:30
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Gregory J. Puleo, Adrian Keister, Paul Frost, Cesareo, clathratus
If this question can be reworded to fit the rules in the help center, please edit the question.
1
$begingroup$
I made a real effort to solve the problem myself, but I thought nobody would be interested to know how many times I tried to find a cycle or how many different ways I used to remove the vertices, because none of that worked :)
$endgroup$
– Haris
Jan 23 at 21:53
$begingroup$
It has a Hamiltonian path that doesn't end in the same place or started.
$endgroup$
– Matt Samuel
Jan 23 at 22:27
1
$begingroup$
Just an idea, I haven't tried this. Clearly edges AC and AB must belong to any Hamilton cycle, so we can delete vertex A and replace it by an edge BC. Similarly, vertices I,M, and P can be replaced by edges, resulting in a cubic graph with 12 vertices. Now, if it can be shown the edges of this graph cannot be three-colored, the graph can have no Hamilton cycle, for we could color the edges of the cycle alternately blue and red, and then color the remaining edges green.
$endgroup$
– saulspatz
Jan 23 at 23:08
1
$begingroup$
Following up on the above comment of @saulspatz -- Since edges AB and BM must appear (in a cycle), the other edge BD from B cannot appear. On the other end, since edges IJ and JP must appear, edge JH cannot appear. Now vertex D only has two possible edges out remaining, i.e.DC and DK, both of which must appear. Similarly vertex H only has edges HG and HL remaining, both of which must appear. If we look at vertex C, two edges AC,CD already used so cannot use edge CE. And looking at vertex G, get that edge GE is no. This leaves vertex E with only one possible edge out of it, so no Hamiltoniancyc
$endgroup$
– coffeemath
Jan 24 at 5:40
$begingroup$
@saulspatz Since question on hold, I'd appreciate it if you could look over my comment above and let me know if you think it works to show not Hamiltonian. Thanks.
$endgroup$
– coffeemath
Jan 24 at 17:13
add a comment |
2
2
2
0
$begingroup$
How to prove this graph is not Hamiltonian (does not contain a Hamiltonian cycle)?
I have already tried removing some vertices from the graph, but I cannot get more than 7 connected components after 7 removed vertices.
Another way was to try to prove it by contradiction, and to assume it has Hamiltonian cycle. The problem is it seems too complex and I have no idea how to try and contradict it.
The actual question was to check if this graph is Hamiltonian, and if yes to draw the cycle, if not to prove it is not Hamiltonian. It is obvious that there is no Hamiltonian cycle, but how to prove it, because removing vertices does not work?
Thanks!
graph-theory hamiltonian-path
asked Jan 23 at 21:20
HarisHaris
263
$endgroup$
How to prove this graph is not Hamiltonian (does not contain a Hamiltonian cycle)?
I have already tried removing some vertices from the graph, but I cannot get more than 7 connected components after 7 removed vertices.
Another way was to try to prove it by contradiction, and to assume it has Hamiltonian cycle. The problem is it seems too complex and I have no idea how to try and contradict it.
The actual question was to check if this graph is Hamiltonian, and if yes to draw the cycle, if not to prove it is not Hamiltonian. It is obvious that there is no Hamiltonian cycle, but how to prove it, because removing vertices does not work?
Thanks!
graph-theory hamiltonian-path
graph-theory hamiltonian-path
asked Jan 23 at 21:20
HarisHaris
263
asked Jan 23 at 21:20
HarisHaris
263
edited Jan 23 at 21:57
Haris
asked Jan 23 at 21:20
HarisHaris
263
asked Jan 23 at 21:20
HarisHaris
263
asked Jan 23 at 21:20
HarisHaris
263
263
closed as off-topic by Gregory J. Puleo, Adrian Keister, Paul Frost, Cesareo, clathratus Jan 24 at 3:30
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Gregory J. Puleo, Adrian Keister, Paul Frost, Cesareo, clathratus
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Gregory J. Puleo, Adrian Keister, Paul Frost, Cesareo, clathratus Jan 24 at 3:30
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Gregory J. Puleo, Adrian Keister, Paul Frost, Cesareo, clathratus
If this question can be reworded to fit the rules in the help center, please edit the question.
1
$begingroup$
I made a real effort to solve the problem myself, but I thought nobody would be interested to know how many times I tried to find a cycle or how many different ways I used to remove the vertices, because none of that worked :)
$endgroup$
– Haris
Jan 23 at 21:53
$begingroup$
It has a Hamiltonian path that doesn't end in the same place or started.
$endgroup$
– Matt Samuel
Jan 23 at 22:27
1
$begingroup$
Just an idea, I haven't tried this. Clearly edges AC and AB must belong to any Hamilton cycle, so we can delete vertex A and replace it by an edge BC. Similarly, vertices I,M, and P can be replaced by edges, resulting in a cubic graph with 12 vertices. Now, if it can be shown the edges of this graph cannot be three-colored, the graph can have no Hamilton cycle, for we could color the edges of the cycle alternately blue and red, and then color the remaining edges green.
$endgroup$
– saulspatz
Jan 23 at 23:08
1
$begingroup$
Following up on the above comment of @saulspatz -- Since edges AB and BM must appear (in a cycle), the other edge BD from B cannot appear. On the other end, since edges IJ and JP must appear, edge JH cannot appear. Now vertex D only has two possible edges out remaining, i.e.DC and DK, both of which must appear. Similarly vertex H only has edges HG and HL remaining, both of which must appear. If we look at vertex C, two edges AC,CD already used so cannot use edge CE. And looking at vertex G, get that edge GE is no. This leaves vertex E with only one possible edge out of it, so no Hamiltoniancyc
$endgroup$
– coffeemath
Jan 24 at 5:40
$begingroup$
@saulspatz Since question on hold, I'd appreciate it if you could look over my comment above and let me know if you think it works to show not Hamiltonian. Thanks.
$endgroup$
– coffeemath
Jan 24 at 17:13
add a comment |
1
$begingroup$
I made a real effort to solve the problem myself, but I thought nobody would be interested to know how many times I tried to find a cycle or how many different ways I used to remove the vertices, because none of that worked :)
$endgroup$
– Haris
Jan 23 at 21:53
$begingroup$
It has a Hamiltonian path that doesn't end in the same place or started.
$endgroup$
– Matt Samuel
Jan 23 at 22:27
1
$begingroup$
Just an idea, I haven't tried this. Clearly edges AC and AB must belong to any Hamilton cycle, so we can delete vertex A and replace it by an edge BC. Similarly, vertices I,M, and P can be replaced by edges, resulting in a cubic graph with 12 vertices. Now, if it can be shown the edges of this graph cannot be three-colored, the graph can have no Hamilton cycle, for we could color the edges of the cycle alternately blue and red, and then color the remaining edges green.
$endgroup$
– saulspatz
Jan 23 at 23:08
1
$begingroup$
Following up on the above comment of @saulspatz -- Since edges AB and BM must appear (in a cycle), the other edge BD from B cannot appear. On the other end, since edges IJ and JP must appear, edge JH cannot appear. Now vertex D only has two possible edges out remaining, i.e.DC and DK, both of which must appear. Similarly vertex H only has edges HG and HL remaining, both of which must appear. If we look at vertex C, two edges AC,CD already used so cannot use edge CE. And looking at vertex G, get that edge GE is no. This leaves vertex E with only one possible edge out of it, so no Hamiltoniancyc
$endgroup$
– coffeemath
Jan 24 at 5:40
$begingroup$
@saulspatz Since question on hold, I'd appreciate it if you could look over my comment above and let me know if you think it works to show not Hamiltonian. Thanks.
$endgroup$
– coffeemath
Jan 24 at 17:13
1
1
$begingroup$
I made a real effort to solve the problem myself, but I thought nobody would be interested to know how many times I tried to find a cycle or how many different ways I used to remove the vertices, because none of that worked :)
$endgroup$
– Haris
Jan 23 at 21:53
$begingroup$
I made a real effort to solve the problem myself, but I thought nobody would be interested to know how many times I tried to find a cycle or how many different ways I used to remove the vertices, because none of that worked :)
$endgroup$
– Haris
Jan 23 at 21:53
$begingroup$
It has a Hamiltonian path that doesn't end in the same place or started.
$endgroup$
– Matt Samuel
Jan 23 at 22:27
$begingroup$
It has a Hamiltonian path that doesn't end in the same place or started.
$endgroup$
– Matt Samuel
Jan 23 at 22:27
1
1
$begingroup$
Just an idea, I haven't tried this. Clearly edges AC and AB must belong to any Hamilton cycle, so we can delete vertex A and replace it by an edge BC. Similarly, vertices I,M, and P can be replaced by edges, resulting in a cubic graph with 12 vertices. Now, if it can be shown the edges of this graph cannot be three-colored, the graph can have no Hamilton cycle, for we could color the edges of the cycle alternately blue and red, and then color the remaining edges green.
$endgroup$
– saulspatz
Jan 23 at 23:08
$begingroup$
Just an idea, I haven't tried this. Clearly edges AC and AB must belong to any Hamilton cycle, so we can delete vertex A and replace it by an edge BC. Similarly, vertices I,M, and P can be replaced by edges, resulting in a cubic graph with 12 vertices. Now, if it can be shown the edges of this graph cannot be three-colored, the graph can have no Hamilton cycle, for we could color the edges of the cycle alternately blue and red, and then color the remaining edges green.
$endgroup$
– saulspatz
Jan 23 at 23:08
1
1
$begingroup$
Following up on the above comment of @saulspatz -- Since edges AB and BM must appear (in a cycle), the other edge BD from B cannot appear. On the other end, since edges IJ and JP must appear, edge JH cannot appear. Now vertex D only has two possible edges out remaining, i.e.DC and DK, both of which must appear. Similarly vertex H only has edges HG and HL remaining, both of which must appear. If we look at vertex C, two edges AC,CD already used so cannot use edge CE. And looking at vertex G, get that edge GE is no. This leaves vertex E with only one possible edge out of it, so no Hamiltoniancyc
$endgroup$
– coffeemath
Jan 24 at 5:40
$begingroup$
Following up on the above comment of @saulspatz -- Since edges AB and BM must appear (in a cycle), the other edge BD from B cannot appear. On the other end, since edges IJ and JP must appear, edge JH cannot appear. Now vertex D only has two possible edges out remaining, i.e.DC and DK, both of which must appear. Similarly vertex H only has edges HG and HL remaining, both of which must appear. If we look at vertex C, two edges AC,CD already used so cannot use edge CE. And looking at vertex G, get that edge GE is no. This leaves vertex E with only one possible edge out of it, so no Hamiltoniancyc
$endgroup$
– coffeemath
Jan 24 at 5:40
$begingroup$
@saulspatz Since question on hold, I'd appreciate it if you could look over my comment above and let me know if you think it works to show not Hamiltonian. Thanks.
$endgroup$
– coffeemath
Jan 24 at 17:13
$begingroup$
@saulspatz Since question on hold, I'd appreciate it if you could look over my comment above and let me know if you think it works to show not Hamiltonian. Thanks.
$endgroup$
– coffeemath
Jan 24 at 17:13
add a comment |
0
active
oldest
votes
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
1
$begingroup$
I made a real effort to solve the problem myself, but I thought nobody would be interested to know how many times I tried to find a cycle or how many different ways I used to remove the vertices, because none of that worked :)
$endgroup$
– Haris
Jan 23 at 21:53
$begingroup$
It has a Hamiltonian path that doesn't end in the same place or started.
$endgroup$
– Matt Samuel
Jan 23 at 22:27
1
$begingroup$
Just an idea, I haven't tried this. Clearly edges AC and AB must belong to any Hamilton cycle, so we can delete vertex A and replace it by an edge BC. Similarly, vertices I,M, and P can be replaced by edges, resulting in a cubic graph with 12 vertices. Now, if it can be shown the edges of this graph cannot be three-colored, the graph can have no Hamilton cycle, for we could color the edges of the cycle alternately blue and red, and then color the remaining edges green.
$endgroup$
– saulspatz
Jan 23 at 23:08
1
$begingroup$
Following up on the above comment of @saulspatz -- Since edges AB and BM must appear (in a cycle), the other edge BD from B cannot appear. On the other end, since edges IJ and JP must appear, edge JH cannot appear. Now vertex D only has two possible edges out remaining, i.e.DC and DK, both of which must appear. Similarly vertex H only has edges HG and HL remaining, both of which must appear. If we look at vertex C, two edges AC,CD already used so cannot use edge CE. And looking at vertex G, get that edge GE is no. This leaves vertex E with only one possible edge out of it, so no Hamiltoniancyc
$endgroup$
– coffeemath
Jan 24 at 5:40
$begingroup$
@saulspatz Since question on hold, I'd appreciate it if you could look over my comment above and let me know if you think it works to show not Hamiltonian. Thanks.
$endgroup$
– coffeemath
Jan 24 at 17:13