---
tag: CJXGKY5WMQ
kind: concept
name: Graceful labeling
aliases: [graceful-graph, graceful-labeling-conjecture, ringel-kotzig-conjecture, von-kochs-conjecture]
sources:
  - wikipedia: en:8978968@r1365285331
    locator: Graceful labeling
    note: adopted
    mention: wikipedia://en/8978968
    sections: [Summary]
same_as:
  wikidata: Q1386718
  wikipedia: Graceful labeling
inventory: [B1PEJ13DT0]
---

## Summary

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