4 Let G V E be the infinite graph given by V Z and Efxyxy1

4. Let G = (V, E) be the (infinite) graph given by V = Z and E=f{(x,y)|x=y+1 or x=y-1}. Thus the degree of each vertex is exactly 2. (a) Prove that G is connected. (b) How many paths are there of length ell from 0 to 0? (Hint: If l is odd, there are no such paths.) (c) How many paths are there of length |k|+ell from 0 to k? (Here k is an integer.)

Solution

a) G is connected as degree of vertex = 2

b) Paths of length l are if l is odd no path

there can be 2 or 4 or 6.... paths from 0 to 0

c) From 0 to k |k|+l length