In this paper, we address the challenge of differential privacy in the context of graph cuts, specifically focusing on the multiway cut and the minimum \(k\)-cut. We introduce edge-differentially private algorithms that achieve nearly optimal performance for these problems. Motivated by multiway cut, we propose the shifting mechanism, a general framework for private combinatorial optimization problems. This framework allows us to develop an efficient private algorithm with a multiplicative approximation ratio that matches the state-of-the-art non-private algorithm, improving over previous private algorithms that have provably worse multiplicative loss. We then provide a tight information-theoretic lower bound on the additive error, demonstrating that for constant \(k\), our algorithm is optimal in terms of the privacy cost. The shifting mechanism also allows us to design private algorithm for the multicut and max-cut problems, with runtimes determined by the best nonprivate algorithms for these tasks. For the minimum \(k\)-cut problem we use a different approach, combining the exponential mechanism with bounds on the number of approximate \(k\)-cuts to get the first private algorithm with optimal additive error of \(O(k \log n)\) (for a fixed privacy parameter). We also establish an information-theoretic lower bound that matches this additive error. Furthermore, we provide an efficient private algorithm even for non-constant \(k\), including a polynomial-time 2-approximation with an additive error of \(\tilde O(k^{1.5})\).