AbstractWe propose a new statistical approach for characterizing the class separability degree in ℝp. This approach is based on a non‐parametric statistic called ‘the cut edge weight’. We show in this paper the principle and the experimental applications of this statistic. First, we build a geometrical connected graph like Toussaint's Relative Neighbourhood Graph on all examples of the learning set. Second, we cut all edges between two examples of a different class. Third, we compute the relative weight of these cut edges. If the relative weight of the cut edges is in the expected range of a random distribution of the labels on all the neighbourhood of the graph's vertices, then no neighbourhood‐based method provides a reliable prediction model. We will say then that the classes to predict are non‐separable. Copyright © 2005 John Wiley & Sons, Ltd.