We consider in this paper an alternative model for the graph partitioning problem in a weighted graph $G=(V,E)$ ($|V|=n$, $|E|=m$) that makes use of only $m$ binary decision variables $(x_e)_{e\in E}$ which are equal to $1$ iff the end-nodes of $e$ are in different clusters, together with the so-called \textit{cycle inequalities} defined on them.
We prove that the node partitions and thus the knapsack constraints can be defined using all pair shortest path of $G$ with respect to the weights $(x_e)_{e\in E}$. The result is a $m$ 0/1 variable programming model for GPKC. This model is referred to as the \textit{cycle model} and it is shown to be equivalent to the Node-Node model. From our computational experiments, it will be shown that this model yields considerable improvement in computational efficiency in case of sparse graphs where $m\ll \frac{n(n-1)}{2}$. Note that since there is a priori no known polynomial upper bound (in terms of $n$ and $m$) on the number of cycles and of paths of the graph $G$, the cycle model has a priori an exponential number of inequalities thus a cutting-plane algorithm is needed to make the computations possible. We introduce such an algorithm which can determine both violated cycle inequalities and violated knapsack constraints via the computations of all pair shortest path of $G$ with respect to the weights $(x_e)_{e\in E}$.