# Proof: By Induction

The if-statement in the steps $$9$$ to $$12$$ of the algorithm $$\mathtt{getCOMPONENT(G,v,m)}$$ makes sure that in the algorithm visits only the vertices connected to $$v$$.

In order to prove that the algorithm visits all such vertices, i.e. that $$G'$$ contains all vertices $$n$$ in $$G$$ connected to $$v$$, follows by induction on the length $$k$$ of the path from $$v$$ to a vertex $$n$$

### Base case

For $$k=0$$ we have trivially $$u=v$$.

### Induction step

Let $$v$$ and $$u$$ be connected, i.e, for $$k\ge 0$$, $$P^k$$ be the path from $$v$$ to $$u$$: $P^k:=x_0x_1\ldots x_{k-1}x_k$

with $$x_0:=v$$ and $$x_k=u$$. The for-next loop in the lines $$8$$ to $$13$$ iterates over all neighbors of $$u$$, which have not yet been visited in the algorithm. Therefore, each such neighbor $$n$$ is not yet in $$P^k$$. Thus, we can add $$n$$ to $$P_k$$ creating an even longer path from $$v$$ to $$n$$, i.e.

$P^{k+1}:=x_0x_1\ldots x_{k-1}x_kx_{k+1}$

with $$x_0:=v$$, $$x_k=u$$ and $$x_{k+1}=n$$. Therefore, $$v$$ is connected with $$n$$.

Thank you to the contributors under CC BY-SA 4.0!

Github:

### References

#### Bibliography

1. Krumke S. O., Noltemeier H.: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition
2. Diestel, Reinhard: "Graph Theory, 3rd Edition", Springer, 2005