پیش‌نویس:قضیه اردوش گالای

قضیه اردوش گالای نتیجه‌ای در نظریه گراف ، شاخه ای از ریاضیات ترکیبی است. یکی از دو رویکرد شناخته شده برای حل مسئله گرافیک بودن دنباله درجات را ارائه می دهد، یعنی شرط لازم و کافی را برای یک دنباله متناهی از اعداد صحیح غیرمنفی می دهد که دنباله درجات یک گراف ساده باشد. این قضیه در سال 1960 توسط پال اردوش و تیبور گالای منتشر شد که به نام آنها نامگذاری شده است.

شرح قضیه

دنباله ای از اعداد صحیح غیر منفی $d_{1}\geq \cdots \geq d_{n}$ را می توان به عنوان دنباله درجه یک گراف ساده متناهی n راسی در نظر گرفت اگر و فقط اگر $d_{1}+\cdots +d_{n}$ زوج باشد و

$\sum _{i=1}^{k}d_{i}\leq k(k-1)+\sum _{i=k+1}^{n}\min(d_{i},k)$

برای هر $1\leq k\leq n$ برقرار باشد.

اثبات‌ها

نشان دادن اینکه شرایط قضیه Erdős-Gallai برای گرافیکی بودن دنباله‌ای از اعداد لازم است دشوار نیست. شرط زوج بودن مجموع درجات، لمای قیاس منطقی دست به دست است که قبلاً توسط اویلر در مقاله خود در سال 1736 در مورد هفت پل کونیگسبرگ استفاده شده است. نابرابری بین مجموع k بزرگ‌ترین درجه‌ها و مجموع درجات باقی‌مانده را می‌توان با شمارش مضاعف تعیین کرد: سمت چپ مجموع تعداد مجاورت‌ها را در بین k راس های بالاترین درجه، هر یک از این مجاورت ها یا بین دو راس با درجه‌ی زیاد است یا بین یک راس با درجه‌ی زیاد و یک راس با درجه‌ی کم. k(k−1) عبارت سمت راست حداکثر تعداد ممکن یال‌های بین دو راس با درجه زیاد را نشان می دهد و عبارت دیگر در سمت راست، تعداد یال‌هایی را نشان می دهد که دقیقاً یک راس درجه بالایی دارند. بنابراین، بخش دشوارتر اثبات این است که نشان دهیم، برای هر دنباله‌ای از اعداد که از این شرایط پیروی می کنند، گرافی وجود دارد که این دنباله برای آن، دنباله‌ی درجات است.

جستارهای وابسته

• Havel–Hakimi algorithm

منابع

• Aigner, Martin; Triesch, Eberhard (1994), "Realizability and uniqueness in graphs", Discrete Mathematics, 136 (1–3): 3–20, doi:10.1016/0012-365X(94)00104-Q, MR 1313278.
• Barrus, M. D.; Hartke, S. G.; Jao, Kyle F.; West, D. B. (2012), "Length thresholds for graphic lists given fixed largest and smallest entries and bounded gaps", Discrete Mathematics, 312 (9): 1494–1501, doi:10.1016/j.disc.2011.05.001
• Berger, Annabell (2012), The connection between the number of realizations for degree sequences and majorization, arXiv:1212.5443, Bibcode:2012arXiv1212.5443B
• Choudum, S. A. (1986), "A simple proof of the Erdős–Gallai theorem on graph sequences", Bulletin of the Australian Mathematical Society, 33 (1): 67–70, doi:10.1017/S0004972700002872, MR 0823853.
• Erdős, P.; Gallai, T. (1960), "Gráfok előírt fokszámú pontokkal" (PDF), Matematikai Lapok, 11: 264–274
• Mahadev, N. V. R.; Peled, U. N. (1995), Threshold graphs and related topics, Elsevier
• Tripathi, Amitabha; Vijay, Sujith (2003), "A note on a theorem of Erdős & Gallai", Discrete Mathematics, 265 (1–3): 417–420, doi:10.1016/s0012-365x(02)00886-5, MR 1969393
• Tripathi, Amitabha; Venugopalan, Sushmita; West, Douglas B. (2010), "A short constructive proof of the Erdős–Gallai characterization of graphic lists", Discrete Mathematics, 310 (4): 843–844, doi:10.1016/j.disc.2009.09.023, MR 2574834