The (cartesian) square GG of a graph G = (V, E) is a graph with vertex...

Transcribed Image Text:

The (cartesian) square GG of a graph G = (V, E) is a graph with vertex set V x V and an edge between (u, v) and (u', v') if and only if u = u' and {v, v'} € E, or v = v' and {u, u'} E E. The picture below shows a graph and its cartesian square. a b d (a, d) (a, c) (a, b) (a, a) (b, d) (b, c) (b, b) (b, a) (c,d) (c, c) (c, b) (c, a) (d, d) (d, c) (d, b) (d, a) (a) Determine the cartesian square of the graph drawn below, that is, the graph with three vertices u, v, and w, and a single edge {u, v}. [2 marks] U V W (b) For a graph G with n vertices and m edges, find formulas for the number of vertices and edges in GG in terms of n and m. [4 marks] The (cartesian) square GG of a graph G = (V, E) is a graph with vertex set V x V and an edge between (u, v) and (u', v') if and only if u = u' and {v, v'} € E, or v = v' and {u, u'} E E. The picture below shows a graph and its cartesian square. a b d (a, d) (a, c) (a, b) (a, a) (b, d) (b, c) (b, b) (b, a) (c,d) (c, c) (c, b) (c, a) (d, d) (d, c) (d, b) (d, a) (a) Determine the cartesian square of the graph drawn below, that is, the graph with three vertices u, v, and w, and a single edge {u, v}. [2 marks] U V W (b) For a graph G with n vertices and m edges, find formulas for the number of vertices and edges in GG in terms of n and m. [4 marks]