Consider the following directed graph:
I have to find the maximum number of directed edges that go out of vertex $6$ that I can add such that the graph has only $3$ paths with the vertex $2$ as the starting point and vertex $4$ as the end point.
I have to choose an answer among the next options:
A. 1
B. 2
C. 3
D. 4
I realize that no matter what I add out of vertex $6$, I will always have the paths
$$[2, 1, 4]$$
$$[2, 5, 3, 4]$$
That start in $2$ and end in $4$. So I have to find the numbers of directed edges that go out of vertex $6$ that would only add another path that starts in vertex $2$ and ends in vertex $4$. But I don't see how I could do that.
If I add the directed edge $[6, 1]$ we would also have the paths
$$[2, 5, 6, 1, 4]$$
$$[2, 6, 1, 4]$$
so we would have $4$ paths that start in vertex $2$ and end in vertex $4$, while we need $3$ such paths. I think the same things happen if I add other type of edges that go out of vertex $6$. But $0$ is not an option. So what am I doing wrong? I either am looking at this from the wrong angle or I have misunderstood the question.
Best Answer
I agree that adding an edge to vertex 1, 3 or 4 will result in more than three paths from vertex 2 to vertex 4. However, you can also add an edge to vertex 2 or 5. These options will create less paths, since all vertices in a path must be unique so you cannot reenter vertices.