(43) Decide whether the following statements are true or false. (a) If G is a co
ID: 3148011 • Letter: #
Question
(43) Decide whether the following statements are true or false. (a) If G is a connected simple graph and e is an edge of G, then there is a (b) IfG is a connected simple graph and e and f are edges of G, then there (c) If G is a connected simple graph and e, f and g are edges of G, then (d) If G is a connected simple graph and F is a cycle-free set of edges in spanning tree of G that contains e. is a spanning tree of G that contains e and f. there is a spanning tree of G that contains e,fand g. G, then there is a spanning tree of G that contains F.Explanation / Answer
Both are true
a) Find any spanning tree T. Now add edge e to T. This forms a cycle C. Delete an edge g from the cycle from T+e. Now T+e-g is still connected (deleting an edge from a cycle cannot disconnect you) but now has the same number of edges as T. So T+e-g must also be a spanning tree.
b) Do the stuff in part a to find a tree T with edge e. Now add in f, forming a cycle in T+f. Choose an edge h in the cycle that is not e. so T+f-h is a spanning tree with e and f.
Now to prove that we can find an edge h, suppose we cannot. Then the cycle can only have edges e and f. But that means that e and f connect the same pair of vertices... which is impossible in a simple graph.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.