17. A graph has an Euler path if and only if the number of odd-degree vertices is 0 or 2.

18. “R is transitive” is equivalent to “if there are edges x → y and y → z then there is an edge x → z.”

19. The sum of the degrees in a tree with n nodes (for n ≥ 1) is 2(n − 1).

20. The simplest algorithm is to check, for each subset S of the vertex set, whether S is bipartite-proving: i.e., whether every edge has one vertex in S and one vertex outside S. If there is a bipartite-proving S then the graph is bipartite; otherwise the graph is not bipartite. This takes time O(2^{n}m) if there are n vertices and m edges. There are much faster algorithms using depth-first search.

21. C, D, E has weight 9. C, B, A, F, E has weight 9. C, B, D, E has weight 9.

22. The minimum spanning tree includes all edges except v_{3} ↔ v_{4}. The shortest-path tree from v_{1} includes all edges except v_{5} ↔ v_{6}.

23. Let G_{n} be the tree v_{1} ↔ v_{2} ↔ ⋯ ↔ v_{n}, with weight 1 on each edge.

24. If the spanning tree is built in the order v_{1}, v_{2}, v_{3}, …, then every edge is a candidate edge at some point.