Graphs offer a technique to visualize and study relationships and organizational systems, and graph algorithms are effective tools for extracting knowledge from graphs. However, when dealing with large graphs, graph algorithms can become computationally costly, and unfortunately, real-life graphs are enormous and voluminous. Parallelization is a method for reducing the computational cost. This research deals with Karger’s min-cut algorithm, which determines the minimum cut in an unweighted, undirected graph. The main motive of this work is to parallelize Karger’s algorithm using OpenMP, MPI, and CUDA and compare the results to find out which gives optimal results. CUDA is a computing platform that is used to make use of the power of GPUs, whereas, OpenMP facilitates the parallelization of code on multi-core CPUs. MPI is employed for distributed memory systems, allowing for process communication. In addition to parallelizing Karger’s algorithm using the above-mentioned three techniques, this work also analyzes its performance by varying parameters such as computational resources and graph size. The proposed work provides valuable insights on selecting optimal parallelization strategy. The experimental results show that the parallel implementation using MPI improves computational efficiency significantly.