We present theoretical work on the existence of second order isotropic random fields defined on the edges and the vertices of a graph. The edges of such a graph are equipped with a coordinate system which is in one-to-one correspondence with an open interval of the real line.  We use Hilbert space embedding techniques to establish that many of the flexible isotropic covariance models used in spatial statistics are valid (i.e., positive semi-definite) with respect to the geodesic metric induced by the edge coordinate system and a new resistance metric defined on the vertices and edge points of the graph. The validity of these covariance models do not hold, however, over the full parametric range available in Euclidean spaces. Moreover, we show the results for the geodesic metric apply to a much smaller class of linear networks and can not be extended to any graph which have three or more paths connecting two points on the linear network. This is in stark contrast to the resistance metric where we show there is no restriction on the type of graph for which they apply.