  Inspired by Lelek's idea from [Disjoint mappings and the span of spaces,
Fund. Math. 55 (1964), 199 -- 214], we introduce the novel notion of the span
of graphs. Using this, we solve the problem of determining the \emph{maximal
safety distance} two players can keep at all times while traversing a graph.
Moreover, their moves must be made with respect to certain move rules. For this
purpose, we introduce different variants of a span of a given connected graph.
All the variants model the maximum safety distance kept by two players in a
graph traversal, where the players may only move with accordance to a specific
set of rules, and their goal: visit either all vertices, or all edges. For each
variant, we show that the solution can be obtained by considering only
connected subgraphs of a graph product and the projections to the factors. We
characterise graphs in which it is impossible to keep a positive safety
distance at all moments in time. Finally, we present a polynomial time
algorithm that determines the chosen span variant of a given graph.
