This paper presents a new algorithm for image segmentation problem using the concepts of Euler graphs in graph theory. By treating image as an undirected weighted non-planar finite graph (G), image segmentation is handled as graph partitioning problem. The proposed method locates region boundaries or clusters and runs in polynomial time. Subjective comparison and objective evaluation shows the efficacy of the proposed approach in different image domains.