If G = (V, E) is a loop-free connected undirected graph and a, b V, then we

If G = (V, E) is a loop-free connected undirected graph and a, b ˆˆ V, then we define the distance from a to b (or from b to a), denoted d(a, b), as the length of a shortest path (in G) connecting a and b. (This is the number of edges in a shortest path connecting a and b and is 0 when a = b.)
For any loop-free connected undirected graph G = (V, E), the square of G, denoted G2, is the graph with vertex set V (the same as G) and edge set defined as follows: For distinct a, b ˆˆ V, [a, b} is an edge in G2 if d(a, b) ‰¤ 2 (in G). In parts (a) and (b) of Fig. 12.46, we have a graph G and its square.
(a) Find the square of the graph in part (c) of the figure.
(b) Find G2 if G is the graph K1,3.
(c) If G is the graph Kl,n for n ‰¥ 4, how many edges are added to G in order to construct G2?
(d) For any loop-free connected undirected graph G, prove that G2 has no articulation points.

Transcribed Image Text:

b. b. У G? (b) G.