(related to Algorithm: Get the Component Induced by Vertices Connected to a Given Vertex)
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\)
For \(k=0\) we have trivially \(u=v\).
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\).
