  Let $S$ be a subset of a amenable group $G$ such that $e\in S$ and
$S^{-1}=S$. The main result of the paper states that if the Cayley graph of $G$
with respect to $S$ has a certain combinatorial property, then every positive
definite operator-valued function on $S$ can be extended to a positive definite
function on $G$. Several known extension results are obtained as a corollary.
New applications are also presented.
