Summary: A partition of the vertex set of a graph \(G\) is called canonical if every two elements of the partition induce in \(G\) either a disconnected graph or the complement of a disconnected graph. Thus, every canonical partition of the graph \(G\) can be associated with another graph whose vertices are in a one-to-one correspondence with the elements of the partition, whereas the edges with pairs of elements of the partitions induce in \(G\) a subgraph complementary to a disconnected graph. This graph is called a canonical base of the graph \(G\) if the trivial partition (consisting of singletons) is the unique canonical partition of \(G\). We show that the canonical base of an arbitrary graph is unique up to isomorphism. We also suggest a polynomial algorithm for finding the canonical base and discuss applications of canonical partitions in optimal codings of graphs.