93 of 100: Connect the Dots

The path for A is pretty obvious.

Most of the solutions I see so far prove that B is impossible by exhausting possibilities, rather than exploring graph theory, so here is my solution without exhausting possibilities.

Start with any vertex on part B, color it red. Color all adjacent vertices to that red vertex blue. Repeat until the graph is colored such that no two connected vertices share the same color.

The graph should end up with 5 red vertices and 2 blue (or 5 blue and 2 red depending on which vertex you picked first).

Every time you leave a vertex, you must go to a vertex of a different color, because that's how we colored the graph. So our path should visit vertices in alternating colors such as RBRBRBR or BRBRBRB. However, this is impossible due to the colors of our vertices being not 3 of one color and 4 of the other. Thus, graph B does not contain a Hamiltonian Path

You can color graph A as well to check, and it turns out there are 3 of one color and 4 of another color, thus allowing such an alternating color path.

To solve this, we must make 3 vital observations.

1. You cannot revisit a path.

2. Certain paths MUST be taken or else it may be impossible to solve. (Highlighted red)

3. After leaving a 'compulsory path', we are unable to use that path again in the same direction.

1 is easy to prove. After visiting a path, if we revisit it, we would be stuck as we could not go forward or backward, due to the restriction that we must visit each dot once.

To prove 2, we use observation 1.

In A and B, the center path and the paths going away from the rectangle are 'compulsory paths'.

This is because the center path contains a dot, and after visiting the dot, we must exit out the only other way, as we are unable to reuse paths.

The paths extending away are obvious, as there is only one way to get to the dots on that path, so they must be the starting and ending points.

Finally, 3. We can prove this by logic, and observations 1 and 2.

Let's say we have a triangular path ABC. AB is a compulsory path. By Travelling A > B, we are done. If we try to go A > C first, we must go C > B. Although we have gone from A > B, we have failed to use the compulsory path AB. We left the path AB, and are unable to rejoin as we are not allowed to revisit A.

Thus, we can make a conclusion that if we are on the starting point of a compulsory path, we cannot leave the path. Or else, we will not be able to pass by what is inside that path. This is important, as the center paths contain a dot that cannot be missed.

In A, all points are on a compulsory path.(Highlighted green) Thus, by using the 'optional paths' to connect the 'compulsory paths', we are able to solve the question.

However, in B, only 5 are on compulsory paths, and the compulsory paths are all connected.

From 3, we know that if we were to leave the path, it would be impossible to get all points.

But at the same time, if we were to follow the compulsory paths, we would miss 2 points on the side.

$\boxed{A\space is\space possible \\ B\space is \space not}$

(A) can be done easily.

However, (B) is impossible. Three different failing paths are shown.

In Picture A , you can use the diagonal to cut through to the other parallel line and thus visit each dot exactly once. It is vital to observe that first you move down and then you move to the parallel line, unlike in Picture B .

In Picture B , you take the the diagonal cut to the other parallel line immediately and hence you cannot visit each dot only once, you have to atleast visit two dots twice.

Therefore, the answer is Only A .

For A a path is easy to find.

For B it is evident that any such path must start and end on the dangling leaf verfices. Start at the top. From the upper-right corner, if you proceed across the diagonal, then from the lower right you cannot reach all three other vertices without getting stuck. If you proceed to a corner (UL or LR), the only next choice is to LL, and again there are 3 unvisited nodes remaining, any one of which leaves you stuck.

So B is not possible.

A can be traversed quite simply. Let us examine B. Any graph covering path has to begin and end at the top or bottom vertices, i.e starting at the top vertex and ending at the bottom vertex or vice versa, These paths would pass through the two vertices at the opposite corners of the closed figure. But these vertices are also the only neighbors for 3 other vertices which would mean that these vertices would have to be visited more than once in any traversal of the graph.

Since the eulerian path problem (traversing edges without revisiting) is possibly simpler, one could possibly convert the above graph to its dual , (i,e convert edges to vertices and vice-versa)