---
tag: 4G36NH4DAQ
kind: concept
name: Label
sources:
  - wikipedia: en:325802@r1373839425
    locator: Glossary of graph theory, section L
    note: adopted
    mention: wikipedia://en/325802#SD5T
    sections: [Summary]
inventory: [5F6EQK9QG1]
---

## Summary

Information associated with a vertex or edge of a graph. A labeled graph is a graph whose vertices or edges have labels. The terms *vertex-labeled* or *edge-labeled* may be used to specify which objects of a graph have labels. Graph labeling refers to several different problems of assigning labels to graphs subject to certain constraints. See also [[graph coloring|0NCPXH194Y]], in which the labels are interpreted as colors.

In the context of graph enumeration, the vertices of a graph are said to be labeled if they are all distinguishable from each other. For instance, this can be made to be true by fixing a one-to-one correspondence between the vertices and the integers from 1 to the order of the graph. When vertices are labeled, graphs that are isomorphic to each other (but with different vertex orderings) are counted as separate objects. In contrast, when the vertices are unlabeled, graphs that are isomorphic to each other are not counted separately.