Can you visit all pink and gray nodes?
In the following graph, is there a path that visits each node exactly once?
You may start at any node.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
4 solutions
Yeah or 3-4-1-2-9-10-11-12-5-13-6-7-8-14
Log in to reply
We both made similar mistakes! There is no line between 5-13!
There is no clarification that you need to alternate colors on your tour... that was a misleading question
Log in to reply
You don't need to alternate color. This an observation that you can use to find the answer. The color pattern was intentionally selected to help in solving the question. ( color theory).
If you follow the path in number order you would realize that when you reach grey node 13 you wound not be able to reach 14 without going to another node that wasn't already visited
That's not a complete solution. The question doesn't ask for any particular order.
It is easy to see that there is more then one node whit an odd number of lines going into it, but for it to be possible to visit each node once, there must be exactly one node with an odd number of lines that goes into it. Therefore the answer is no.
No. Your argument is valid when you are solving the salesman problem and you want to get back to the starting node.
No, it won’t. Ossama Ismail is correct. Consider a square with a node at each corner and one diagonal. It is possible to trace all edges (but not to return to the start node), but there are two nodes with an odd number of edges attached.
Log in to reply
Thank you for pointing this out. I, too, got it right for the wrong reason.
That is for when you want to trace all lines exactly once.
Log in to reply
Yes and it isn't one node with an odd number of edges, it is two nodes with an odd number of edges which represent the start and end nodes.
I'm sorry but this argument makes no sense. If you have a cycle graph, all the nodes have an even number of edges, but you can create a path which visits every node exactly once by moving along all of the edges.
There is something like what you said but:
A. It applies to paths that visit every edge once, not every node once.
B. The argument says that you need two nodes with an odd number of edges, not one.
In fact it is not possible for a simple graph to have any odd number of nodes with an odd number of edges (including 1 node). I'm going that the number of nodes in a simple graph which has an odd number of edges, must be even using induction (from now on, I will call to a node in the graph which has an odd number of edges connected to it, an odd nodes for convenience):
first of all the empty graph and the graph with only one node, both contain 0 odd nodes (the empty graph because it doesn't contain any node, and the 1 node graph, because there isn't any additional node for the node of the graph to connect to, and so its number of edges must be 0).
Now for a simple graph there are only 2 operations available to expand the graph:
1. Create a new node and connect it by edge to an existing node.
2. Connect two existing nodes with an edge.
I am going to prove that no matter what, both of these operations, either:
1. Increase the number of odd nodes by 2.
2. Decrease the number of odd nodes by 2
3. Leave the number of odd nodes the same.
If this is true, this means that the parity of the number of odd nodes in simple graph doesn't change, which means that the number of odd nodes in the graph remains even (because it started even with the empty and 1 node graphs), which means that the number of odd nodes in a simple graph can never be an odd number.
First let's start with the operation of creating another node, and connecting it by edge to an existing node:
The new node, is guaranteed to be an odd node, because it only has one edge (the edge we now created), and so there are two possibilities to what would happen to the number of odd nodes depending of whenever or not the existing node was an odd node or not:
1. If the existing node was already an odd node, then it becomes a non odd node, meaning the number of odd nodes on a graph doesn't change.
2. If the existing node wasn't an odd node, then it becomes an odd node, and so the number odd nodes in the graph, increases by 2.
Now, I will prove that connecting two existing nodes by an edge, also either increases the number of odd edges, by 2, decreases it by 2, or keeps it the same:
When connecting two existing nodes with an edge, there are 3 possibilities:
1. If both nodes were and odd nodes, then now they both will be a non odd nodes, because they both acquired an additional edge and so the number of edges they are connected to, turned from odd to even, and so the number of odd nodes decreases by 2.
2. If both nodes were a non odd nodes, then now they both will be an odd nodes, because they both acquired an additional edge and so the number of edges they are connected to, turns from even to odd, and so the number of odd nodes increases by 2.
3. If one node was an odd node, and the other wasn't, then the odd node becomes a non odd node, (because acquiring the additional edge turned the number of edges it is connected to from odd to even), and the non odd node becomes an odd node (because acquiring the additional edge turned the number of edges it is connected to from even to odd) which means that the total number of odd nodes in the graph, doesn't change.
So know we know that both of the operations available to simple graph either:
1. Increase the number of odd nodes by 2.
2. Decrease the number of odd nodes by 2.
3. Leave the number of odd nodes the same.
This completes the proof, because according to the line of reasoning I wrote earlier, it means that for any simple graph, the number of odd nodes cannot odd.
Q.E.D.
P.S: for anyone wondering, the proof does not work for multigraphs. This is because for multigraphs, there is an additional operation available to expand the graph, connect a node to itself. This operation turns an odd node to a non odd node, and a non odd node to an odd node, and so it either increases or decreases the number of odd nodes in the graph by 1, and so it does change the parity of the number of odd nodes in the graph, and so a multigraph can have an odd number of odd nodes.
Actually we have to find a Hamiltonian Path of the graph.For a Hamiltonian Graph of a graph with vertices n each vertex should have a degree with ≥ n / 2 .Here vertex 1 has vdegree 3 so there will be no Hamiltonian Path
Are you sure that each vertex needs to have degree ≥ n / 2 ? A cycle on n vertices would visit every vertex exactly once, and the degree of each vertex is only 2.
You refer to a theorem of Dirac which describes a sufficient condition, not a nessecary condition.
a cube has degree 3 < (8/2) but still has a Hamiltonian path.
no easy way to tell from the graph right away whether it has a Hamiltonian path or not. Best is to do it by inspection :)
There is no clarification that you need to alternate colors on your tour... that was a misleading question.
Log in to reply
There is no such requirement, only a natural consequence of the state of this system, where no pink is connected to another pink and no gray connected to another gray. Therefore, when moving from one node to another, you will necessarily be alternating colors.
The answer is NO.
In this graph, we have 14 nodes. In any possible tour, the path will have one of following patterns:
p i n k − g r a y − p i n k − g r a y − p i n k − g r a y − p i n k − g r a y − p i n k − g r a y − p i n k − g r a y − p i n k − g r a y .
or
g r a y − p i n k − g r a y − p i n k − g r a y − p i n k − g r a y − p i n k − g r a y − p i n k − g r a y − p i n k − g r a y − p i n k .
But in this graph, you have EIGHT gray and SIX pink. So it is impossible to complete your tour.