Proofs

Question 1

If a graph contains a u-v walk of length l, then it contains a u-v path of length at most l, provided u!=v

Answer 1

Step 1: Consider W = (u1=u,u2,…uk=v) to be the shortest u-v walk in G. k<=l
Step 2: Assume: W is not a path. Which mean, at some point a vertex repeats itself. i.e. ui=uj where 0<=i<=j<=k
Step 3: Since the vertex ui repeats itself, we can remove the excess vertices. The excess vertices are i+i to jth vertex.
Removing these, makes it a shorter walk than W. i.e u-v walk shorter than W.
Hence it contradicts.
Hence, the assumption is false i.e. W is a path.

https://www.youtube.com/watch?v=728bZWwTbf8&list=PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH&index=16

Question 2

A connected graph has exactly one component

Question 3

Every disconnected graph has atleast two components.

Question 4

A graph with n vertices and m edges, will have atleast n-m components

Answer 4

If m=0, it will have n-0=n components.
If an edge is added, it will reduce the number of components by atmost 1.
- If the added edge is within an existing component, it does not reduce.
- If added edge is across two components, the number of components reduce by one.