Definition:Labeled Graph

From ProofWiki
Jump to navigation Jump to search


A labeled graph is a graph whose vertices are each assigned an element from a set of symbols (letters, usually, but this is unimportant).

The important thing to note is that the vertices can be distinguished one from another.

Note that it is not necessary for all the vertices to be assigned different labels.

A vertex-colored graph can be considered as a labeled graph, in which the labels assigned are elements from a set of colors. In this context it is then rare that all vertices are required to be assigned different colors.

A graph which has no such labeling is called an unlabeled graph.