$[$ Graph algorithms$]$

a$.(5$ pts$)$ If a topological sort exists for the vertices in a directed graph, then a DFS

on the graph will produce no back edges. $($True$/$False$)?$ Explain

b$.(10$ pts$)$ A depth$-$first search of a directed graph always produces the same

number of tree edges $($i$.$e$.$ independent of the order in which the vertices are

provided and independent of the order of the adjacency lists$).$ True or False?

Explain your answer.

c$.(10$ pts$)[$ Graph algorithms$-$bipartite$]$ When do you say a graph is bi$-$partite?

How would you determine it$?$

d$.(5$ pts$)$ This graph below has at least one valid topological ordering. True or