The paper addresses the issue of protecting individual identities in graph data by proposing a graph-anonymization framework. The authors define a graph as $k$-degree anonymous if every node has at least $k-1$ other nodes with the same degree, preventing re-identification by adversaries with prior knowledge of node degrees. They formalize the problem of finding the $k$-degree anonymous graph with the minimum number of edge modifications and devise efficient algorithms based on degree sequence realizability. The algorithms are tested on synthetic and real datasets, demonstrating their effectiveness and practical utility. The paper also discusses related work and provides a detailed overview of the proposed approach, including the degree anonymization and graph construction problems. Additionally, it introduces a relaxed version of the graph construction problem and presents algorithms for solving it, along with experimental results showing the performance of the proposed methods.The paper addresses the issue of protecting individual identities in graph data by proposing a graph-anonymization framework. The authors define a graph as $k$-degree anonymous if every node has at least $k-1$ other nodes with the same degree, preventing re-identification by adversaries with prior knowledge of node degrees. They formalize the problem of finding the $k$-degree anonymous graph with the minimum number of edge modifications and devise efficient algorithms based on degree sequence realizability. The algorithms are tested on synthetic and real datasets, demonstrating their effectiveness and practical utility. The paper also discusses related work and provides a detailed overview of the proposed approach, including the degree anonymization and graph construction problems. Additionally, it introduces a relaxed version of the graph construction problem and presents algorithms for solving it, along with experimental results showing the performance of the proposed methods.