In graph theory, a **graceful labeling** of a graph with *e* edges is a labeling of its vertices with some subset of the integers between 0 and *e* inclusive, such that no two vertices share a label, and such that each edge is uniquely identified by the positive, or absolute difference between its endpoints. A graph which admits a graceful labeling is called a **graceful graph**.

The name "graceful labeling" is due to Solomon W. Golomb; this class of labelings was originally given the name **β-labelings** by Alex Rosa in a 1967 paper on graph labelings.

A major unproven conjecture in graph theory is the **Ringel–Kotzig conjecture**, named after Gerhard Ringel and Anton Kotzig, which hypothesizes that all trees are graceful. The Ringel-Kotzig conjecture is also known as the "graceful labeling conjecture". Kotzig once called the effort to prove the conjecture a "disease".

Read more about Graceful Labeling: Selected Results

### Other articles related to "graceful labeling, graceful, labeling":

**Graceful Labeling**- Selected Results

... Eulerian graph with number of edges m ≡ 1 (mod 4) or m ≡ 2 (mod 4) can't be

**graceful**... his original paper, Rosa proved that the cycle Cn is

**graceful**if and only if n ≡ 0 (mod 4) or n ≡ 3 (mod 4) ... All path graphs and caterpillar graphs are

**graceful**...

**Graceful Labeling**

... A graph is known as

**graceful**when its vertices are labeled from 0 to, the size of the graph, and this

**labeling**induces an edge

**labeling**from 1 to ... Thus, a graph is

**graceful**if and only if there exists an injection that induces a bijection from E to the positive integers up to ... paper, Rosa proved that all eulerian graphs with order equivalent to 1 or 2 (mod 4) are not

**graceful**...

### Famous quotes containing the words labeling and/or graceful:

“Although adults have a role to play in teaching social skills to children, it is often best that they play it unobtrusively. In particular, adults must guard against embarrassing unskilled children by correcting them too publicly and against *labeling* children as shy in ways that may lead the children to see themselves in just that way.”

—Zick Rubin (20th century)

“Personal size and mental sorrow have certainly no necessary proportions. A large bulky figure has a good a right to be in deep affliction, as the most *graceful* set of limbs in the world. But, fair or not fair, there are unbecoming conjunctions, which reason will pa tronize in vain,—which taste cannot tolerate,—which ridicule will seize.”

—Jane Austen (1775–1817)