# Unique Partition of a Graph

Given an undirected graph, is it possible to find a criteria that leads to a unique partition of the nodes? The graph is not weighted.

• The loose phrase "community detection" seems relevant, breaking the graph up into subgraphs where a node is more closely related to nodes in its partition than to those in other partitions. A variety of criteria can be used to define what "closely related" means. Apr 6 '13 at 0:18
• It's unclear what sort of criteria you have in mind. Of course it's possible to partition the nodes of a graph in many ways, in particular by placing each node in its own subgraph (or somewhat less trivially, by using connected components to partition the graph). What do you mean by "leads to a unique partition"? Apr 7 '13 at 1:13

## 1 Answer

This is impossible unless the graph is somehow labeled. For example, consider the complete graph $G = K_{2n}$ consisting of $2n$ vertices and edges between every pair of vertices. All balanced partitions look exactly the same in terms of this graph, so it is not possible to pick one out uniquely.