给定图 G 和 DFS 树中的前向边 (u,v)，证明 G 存在一棵 DFS 树，其中边 (u,v) 是树边。
我的解决方案：(u,v) 是前向边，因此这意味着 (u,v) 是 G 中的边。我们将运行 DFS(u) 并选择 v 作为我们在 u 之后访问的第一个顶点，所以 ( u,v) 将是该 dfs 树中的树边。
我刚刚在这个解决方案上打了一个大X，说“证明是错误的”。我找不到什么问题。
这个问题有点不清楚。但我假设你需要证明你构建的新 DFS 树也可以访问图中的所有顶点。否则，这个问题是没有意义的，因为你可以说 DFS 树只包含前向边缘而没有其他内容。
你的想法很接近，但你可以证明有一种方法可以删除一条边并向原始 DFS 树添加一条边（前向边），使得条件（每个顶点都可以到达并且前向边包含在满足新的 DFS 树）。当然你也必须证明你的主张。