  Although NP-Complete problems are the most difficult decisional problems, it
is possible to discover in them polynomial (or easy) observables. We study the
Graph Partitioning Problem showing that it is possible to recognize in it two
correlated polynomial observables. The particular behaviour of one of them with
respect to the connectivity of the graph suggests the presence of a phase
transition in partitionability.
