In deterministic graphs, assessing whether a graph possesses a specific property is straightforward. However, for an uncertain graph, the answer is not simply an “affirmative” or a “negative”. As an uncertain graph could be viewed as a Boolean dynamic system, the uncertain measure that an uncertain graph has a graph property could be calculated by related operational law in uncertainty theory. This calculation, however, cannot be done in polynomial time. This work focuses on graph properties with edge monotonicity, introducing a polynomial-time algorithm for calculating uncertain measures and distributions of indices in uncertain graphs. The method’s utility is demonstrated through calculating distributions of the clique number in uncertain graphs.