Which is a true statement about all directed graphs with n nodes?

Select one:

a. If the DFS tree from some node has n levels, the graph has a topological ordering.

b. If the BFS tree from some node has n levels, the graph has a topological ordering.

c. If the graph is a DAG, a BFS has no back edge (going from a lower to a higher level).

d. If a DFS has a cross edge, the graph cannot have a unique topological ordering.

e. Trick question, all other four statements are false.

2.

Which of the following statements is true about an undirected graph G?

Select one:

a. If G has an even-length cycle, it is bipartite.

b. If G is bipartite, it is either a tree or it has an even-length cycle.

c. If G is bipartite, we can partition its nodes into two sets X and Y so every node in X has some edge to a node in Y, and every node in Y has an edge to some node in X.

d. If G is connected and bipartite, BFS from every node results in the same number of non-tree edges going between adjacent levels.