graph toughness en · NOUN Meanings (uncountable) A measure, expressed by a positive integer (with the exception of complete graphs), of the connectivity of a graph.