Assign a grade of A (correct), C (partially correct), or F (failure) to each. Justify assignments of grades other than A.
(a) Claim. If v and w are vertices in a graph such that d (u, v) = 3 and d (u, w) = 4, then d (v, w) ≤ 7.
“Proof.” Suppose d (u, v) = 3 and d (u, w) = 4. Then there is a path u, x1, x2, v from u to v with length 3 and a path u, y1, y2, y3, w from u to w with length 4. Then v, x2, x1, u, y1, y2, y3, w is a path from v to w with length 7. The distance from v to w is the length of the shortest path from v to w and there is a path of length 7, so d (v, w) ≤ 7.
(b) Claim. Every connected graph G of order n has a closed path of order n.
“Proof.” Let G be connected graph of order n with vertices x1, x2, x3,…, xn. Since G is connected, each of the vertices is reachable from xi−1 and x1 is reachable from xn .Thus connecting these paths there is a path from x1, to x2,to x3 ,….xn and back to By Theorem 3.5.2(b) the length of any closed path, including this one, is at most n.
Reference:
Theorem 3.5.2 Let G be a graph of order n.
(a) If there is a walk originating at v and terminating at u in a graph G, then there is a path from v to u.
(b) The length of a path in G that is not closed is at most n – 1. The length of a closed path is at most n.
We need at least 10 more requests to produce the solution.
0 / 10 have requested this problem solution
The more requests, the faster the answer.