# Graceful labeling

## Type of graph vertex labeling / From Wikipedia, the free encyclopedia

#### Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about Graceful labeling?

Summarize this article for a 10 years old

In graph theory, a **graceful labeling** of a graph with m edges is a labeling of its vertices with some subset of the integers from 0 to m inclusive, such that no two vertices share a label, and each edge is uniquely identified by the absolute difference between its endpoints, such that this magnitude lies between 1 and m inclusive.[1] A graph which admits a graceful labeling is called a **graceful graph**.

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

A major conjecture in graph theory is the **graceful tree conjecture** or **Ringel–Kotzig conjecture**, named after Gerhard Ringel and Anton Kotzig, and sometimes abbreviated **GTC**.[3]
It hypothesizes that all trees are graceful. It is still an open conjecture, although a related but weaker conjecture known as "Ringel's conjecture" was partially proven in 2020.[4][5][6]
Kotzig once called the effort to prove the conjecture a "disease".[7]

Another weaker version of graceful labelling is **near-graceful labeling**, in which the vertices can be labeled using some subset of the integers on [0, *m* + 1] such that no two vertices share a label, and each edge is uniquely identified by the absolute difference between its endpoints (this magnitude lies on [1, *m* + 1]).

Another conjecture in graph theory is **Rosa's Conjecture**, named after **Alexander Rosa**, which says that all triangular cacti are graceful or nearly-graceful.[8]

A graceful graph with edges 0 to m is conjectured to have no fewer than $\left\lceil {\sqrt {3m+{\tfrac {9}{4}}}}\right\rfloor$ vertices, due to sparse ruler results. This conjecture has been verified for all graphs with 213 or fewer edges.