Finite automata traversing graphs by moving along their edges are known as graph-walking automata (GWA). This paper investigates the state complexity of union and intersection for this model. It is proved that the union of GWA with m and n states, with m⩽ n, operating on graphs with k labels of edge end-points, is representable by a GWA with 2 km+ n+ 1 states, and at least 2 (k- 3 ) (m- 1 ) + n- 1 states are necessary in the worst case. For the intersection, the upper bound is (2 k+ 1 ) m+ n and the lower bound is 2 (k- 3 ) (m- 1 ) + n- 1.