Properly labeling human body parts in video sequences is essential for robust tracking and motion interpretation frameworks. We propose to perform this task by using Graph Matching. The silhouette skeleton is computed and decomposed into a set of segments corresponding to the different limbs. A Graph capturing the topology of the segments is generated and matched against a 3D model of the human skeleton. The limb identification is carried out for each node of the graph, potentially leading to the absence of correspondence. The method captures the minimal information about the skeleton shape. No assumption about the viewpoint, the human pose, the geometry or the appearance of the limbs is done during the matching process, making the approach applicable to every configuration. Some correspondences that might be ambiguous only relying on topology are enforced by tracking each graph node over time. Several results present the efficiency of the labeling, particularly its robustness to limb detection errors that are likely to occur in real situations because of occlusions or low level system failures. Finally the relevance of the labeling in an overall tracking system is described.