In how many ways..?

[Darya]

The problem is to define in how many ways we can plan our 'trip' so that we don't cross go through any line twice.

Is there a quicker way to calculate them apart from trying out all the ways? The task needs to be solved under 2 min. Any hints?

 

[JeffM]

There must be a way to attack this using topology, but I do not know topology.

You can certainly just count, but this is tedious and error prone.

I'd proceed as follows.

To get to D, there are only 2 possible preceding points, B and C. There is just 1 route from B to D, and there are just 2 routes from A to B

Thus, there are 2 routes that skip C.

Now, think about the number of routes to C and the number of routes from C.

 

[HallsofIvy]

Cross "through" any line? Do you mean "go along" any line. First you should state the problem more clearly- I presume it is to pass along any line exactly one- that is, to find an "Euler Circuit". To do that, recall that to pass through any intersection you need a line entering and a line leaving. If you pass through a point more times, you will need an even number of lines terminating at that point. If we start and end at the same point, it also must have an even number of lines- all points must have an even number of lines. If we start at one point and end at another, those two points must have a odd number of lines.

I notice that there is exactly one point, A, that has an odd number of lines. There is NO "Euler Circuit".

 

[pka]

There is an Euler circuit because both \(A~\&~B\) are odd vertices.
\(ABACBCDCDB\) is one such.

 

[Dr.Peterson]

The problem is to define in how many ways we can plan our 'trip' so that we don't cross go through any line twice.

Is there a quicker way to calculate them apart from trying out all the ways? The task needs to be solved under 2 min. Any hints?

You need to copy the problem exactly as given to you, including any previous information that sets it up. In particular, where must "our trip" go (start, end, and intermediate points)?

As has been said, there is no Euler circuit (a path through all edges that starts and ends in the same place). There are Euler paths (paths that use all edges but start and end in different places) from A to B. But you might instead be looking for a Hamiltonian path (through all nodes), or for something else, like any path from A to D.

So, what is the problem, really?

Most likely JeffM's idea is closest to what you need.

 

[pka]

As has been said, there is no Euler circuit (a path through all edges that starts and ends in the same place).

That definition depends on the textbook one uses. SEE HERE
This define An Eulerian trail,[3] or Euler walk in an undirected graph is a walk that uses each edge exactly once. If such a walk exists, the graph is called traversable or semi-eulerian. The Open-University graph theory textbook by Wilson & Watkins uses paths & cycles but never even mentions circuits.