Segmentation is the process of partitioning an image into disjoint and homogeneous regions. It is a fundamental step toward low-level vision, which is significant for object recognition and tracking, image retrieval, face detection, and other computer-vision-related applications. There has been significant interest in graph-based approaches to image segmentation in the past few years. These methods possesses some desirable properties. In particular, both spatial information and feature space characteristics influence the procedure appropriately. In these approaches the image is considered as a whole and all pixels play role in partitioning. Moreover, in some graph-based methods minimization of the inter-region similarity and maximization of the intra-regions similarity are simultaneously accomplished. The common theme underlying these approaches is the formation of a weighted graph where each vertex corresponds to an image pixel and each edge is weighted with some measure of the desire for the pixels connected by that edge to be in the same segment. The weights are usually related to the color and/or texture features, a well a the spatial characteristic of the corresponding ixels. This graph is partitioned into components in a way that minimizes some specified cost function of the vertices in the components and/or the boundary between those components. Till now, several cost functions are proposed for image segmentation. The most popular one is the Normalized cut (Ncut). However, Ncut-based techniques suffer high computation complexity and are not suitable for real-time processing. An efficient solution to this problem is to apply the graph representation strategy on the regions (instead of pixels) that are derived by some region segmentation method. In 2007, Tao, Jin and zhang, proposed to construct a graph in which each vertex is associated with a region derived by Mean-Shift algorithm. They applied Ncut method for partitioning this region-based graph. It is well known that Ncut algorithms try to find a “balanced partition” of a weighted graph, and the cut does not have a bias in favor of cutting small sets of isolated nodes in the graph. But this property is desirable for pixel-based graphs. In region-based graphs, some vertices may correspond to very large regions which must be separated in the first steps. In order to overcome this problem, Tao, Jin and zhang proposed to replace each vertex of the region-based graph by a complete graph and then apply Ncut. Here in this thesis we analytically prove the u Key words Image segmentation, Graph, Spectral clustering, Ncut method, Generalized eigenvalue problem, Rayleigh-Ritz theorem.