An undirected graph is said to be connected if there is a path between any two vertices in the graph. Given a connected undirected graph G = (V, E), where V = {1, . . . , n}, give an algorithm that runs in time O(|V | + |E|) and finds a permutation : [n] 7 [n] such that the subgraph of G induced by the vertices {(1), . . . , (i)} is connected for any i n. Justify briefly the correctness and running time of your algorithm.

An undirected graph is said to be connected if there is a path between any two vertices in the graph. Given a connected undirected graph G = (V,E), where V-(L ,n), give an algorithm that runs in time O(IVI EI) and finds a permutation T : [n] * [n such that the subgraph of G induced by the vertices (1),., (i)) is connected for any i Sn. Justify briefly the correctness and running time of your algorithm