Situations very similar to phase transitions (PTs) have been observed in constraint satisfaction problems. In our analysis, applying the backtracking-based tree search algorithm with Brélaz heuristic to the graph-coloring problems with three colors (3GCPs), we first reconfirmed PT phenomena. We then traced the backtracking history for variables for which thrashing appears to occur in the hardest problems. As a result, we found a local key structure of a graph, or a rigid pair, which is a pair of nodes to each of which the same color must be assigned, and is included in a subgraph such as Fig. l(a) in 3GCPs. We found many rigid pairs in extraordinarily hard problems, in which very heavy trial-and-error repetitions of coloring are performed until the same color is assigned to rigid pairs.