This study attempts to describe characteristics of graph thinking in solving a mathematical problem. Three students at the 10th grade of senior-high schools were involved as the subject. The data was collected from the result of an optimization problem task (OPT), video recording, interviews, and field notes. The results showed two major characteristics of graph thinking were found in solving the problem. First, students used the concept of graph theory to create a problem modelling. They were able to represent the information given in the problem in the form of graph. Second, students also used the concept of graph theory to create a problem modelling and search algorithm. The problem modelling was created as the students interpreted the problem by making connection between the objects in the form of an adjacency matrix and connectivity. In devising a plan, the students referred to the problem modelling to develop search algorithms. However, the algorithms were not entirely efficient. Some of them required the students to initially describe all answer possibilities. The algorithms constructed by the students referred to sequential and conditional algorithms. This study argues that graph-thinking skill can be developed through a learning process which involves students in the solving of open-ended problem to stimulate ideas of problem solving. By developing graph thinking ability, students will be able to analyse and reason information, express mathematical ideas, and have flexibility in solving a problem. These skills are urgently needed in the 21st century where rapid and continuous changes occur.