In Section 4.3.2, it was noted that, for an m × m adjacency matrix represents a matrix where each entry is the number of walks of length n from vertex i to vertex j. Prove by induction that this is...

In Section 4.3.2, it was noted that, for an m × m adjacency matrix

represents a matrix where each entry

is the number of walks of length n from vertex i to vertex j. Prove by induction that this is the case.

Let

be an
vertex,
edge undirected graph, and

be an hvertex, k-edge undirected graph. Consider the direct product graph

(a) How many vertices are in
?

(b) How many edges are in
?

(c) How large is the adjacency matrix for
? What does this say about performing the direct product kernel on large graphs?