2. Definition: A tree is a connected graph with no cycles. Let C(G) be a decider for the language LCONNECTED = {G| G is a simple connected graph}. Prove that the following program T(G) is a decider for the language LTREE {G | G is a tree}. Remember: in order for something to be a decider, it must accept all inputs in the language and reject all inputs that are not in the language. 1. 2. 3. 4. 5. T = on input G: Run C(G) and reject if it rejects For each edge e of G: G' + G without the edge e Run C(G') and reject if C(G') accepts Accept 2. Definition: A tree is a connected graph with no cycles. Let C(G) be a decider for the language LCONNECTED = {G| G is a simple connected graph}. Prove that the following program T(G) is a decider for the language LTREE {G | G is a tree}. Remember: in order for something to be a decider, it must accept all inputs in the language and reject all inputs that are not in the language. 1. 2. 3. 4. 5. T = on input G: Run C(G) and reject if it rejects For each edge e of G: G' + G without the edge e Run C(G') and reject if C(G') accepts Accept