You are right! Luckily that's the definition of a graph property .

Something that definitely won't work: The parity of the number of edges.

Still, it's pretty general.