In this paper, we propose a weighted undirected graph-based video scene detection method. The method is based on the idea of using the complete information of the graph. For this aim, each shot is represented by a vertex on the graph. Edge weights among vertices are evaluated by using spatial and temporal similarities of shots. Only a single video scene boundary which has the highest probability to be the correct one is determined and this scene boundary information is also used as a clue in the next steps. A tree-based peeling strategy is proposed to determine the boundaries of the remaining scenes. In order to test our graph-based video scene detection method, we used DVD chapters' information and promising results were obtained when compared to the results of the similar work presented in literature.