Can I have some example for true or false inputs for question 6, to check myself if I’m in the right direction?
Plus, how any MUXs are expected to be in this solution?
You can use the graph and corresponding adjacency matrix given in Figure 3. Choose any two vertices you like, any number of steps you like, and manually check if there exists a path as required. Then feed the adjacency matrix into your circuit, and check if your output matches what you found based on manual investigation.
Unless specified otherwise, you are allowed to use any number of MUXes. This applies to all exercises, not just this one.