Let G be a graph and δ(G) the minimum degree of a peak. Describe an algorithm in pseudocode that, for a given tree T with k<= δ(G) edges, should be build (in polinomial time) a sub-graph H of G so that H is isomorphic with T.
How do I even start ?
Let G be a graph and δ(G) the minimum degree of a peak. Describe an algorithm in pseudocode that, for a given tree T with k<= δ(G) edges, should be build (in polinomial time) a sub-graph H of G so that H is isomorphic with T.
How do I even start ?
Scan the tree $T$ in some arbitrary way, meanwhile tracing out the subgraph $H$ (start at an arbitrary vertex of $G$). Take care not to close cycles. The condition on the minimum degree ensures that you'll never "run out of edges".