Distance Between Vertices and Connected Components of Graphs


If there is walk (and  hence a path from u to vin given graph G).


dG(u,v)= min { k  | u --- k-->v} be the distance between u and v.


dG(u,v) =∞ by convention ,when thereis no walk


Note: A graph G is connected if dG(u,v) <∞ for all u,v∈G and disconnected otherwise.

The maximal connected sub graphs of G areits connected components

     c(G)=# of connected component of G

here c(G) is 2.


what maximality condition mean is ?

Maximality condition means that a sub graph H ⊆ G is a connected sub graph and for any w ∈ V(G) w ∉ H

then G[V(H) ∪{w}] is disconnected.