گراف‌های پنجه‌آزاد

• گراف یالی ${\displaystyle L(G)}$
  هر گراف ${\displaystyle G}$
  پنجه‌آزاد است؛ ${\displaystyle L(G)}$
  به ازای هر یال ${\displaystyle G}$
  یک راس دارد، و دو راس در ${\displaystyle L(G)}$
  با یکدیگر مجاورند هرگاه یال‌های متناظر آن‌ها در ${\displaystyle G}$
  ، در یک سر خود مشترک باشند. گراف یالی ${\displaystyle L(G)}$
  نمی‌تواند پنجه داشته باشد، زیرا اگر سه یال ${\displaystyle e_1,e_2}$
  و ${\displaystyle e_3}$
  هر سه در ${\displaystyle G}$
  با یال دیگری مثل ${\displaystyle e_4}$
  سر مشترک داشته باشند، طبق اصل لانه‌کبوتر حداقل دوتا از یال‌ها در یک سر مشترک ${\displaystyle e_4}$
  با آن اشتراک دارند و بنابراین با هم مشترک هستند و در ${\displaystyle L(G)}$
  بین آنها یال وجود دارد.
• گراف دی براین (گرافی که به هر راس آن یک کد ${\displaystyle n}$
  بیتی باینری نسبت داده شده‌است و بین دو راسی که ${\displaystyle n-1}$
  هم پوشانی دارند یال وجود دارد) پنجه‌آزاد است.
• مُکمّل هر گراف مثلث-آزاد پنجه‌آزاد است.
• گراف اِشلفلی که ۲۷ راس دارد یک گراف پنجه آزاد است.

بررسی کردن پنجه‌آزاد بودن یا نبودن یک گراف دلخواه با ${\displaystyle n}$

در سال ۲۰۰۰ میلادی، کلاکس، کراتش و مولر به این نتیجه رسیدند که هر رأس در گراف پنجه‌آزاد حداکثر ${\displaystyle 2\sqrt{m}}$

چون مکمل هر گراف مثلث‌آزاد یک گراف پنجه‌آزاد است، رشد تعداد گراف‌های پنجه‌آزاد حداقل به اندازهٔ رشد تعداد گراف‌های مثلث‌آزاد سریع است، به صورت تابعی نمایی بر حسب ${\displaystyle n}$

${\displaystyle 1,1,2,5,14,50,191,881,4494,26389,184749,...}$

((دنباله A022562 در OEIS)).

اگر گراف‌های ناهمبند را هم بشماریم، تعداد باز هم بیشتر می‌شود:

${\displaystyle 1,2,4,10,26,85,302,1285,6170,...}$

((دنباله A086991 در OEIS)).

با بهره بردن از تکنیک Palmer, Read & Robinson می‌توان گراف‌های مکعبی پنجه‌آزاد (گراف مکعبی، همان گراف ۳-منتظم است) را بسیار کارا شمرد که برای مسائل شمارش گراف امری طبیعی نیست.

لاس ورناگس (۱۹۷۵) و سومنر (۱۹۷۴)‌ به‌طور مستقل اثبات کردند که هر گراف زوج رأسی همبند پنجه‌آزاد یک تطابق کامل دارد. یکی از نتایج مهم این نکته در گراف یالی آن است که در هر گراف با تعداد زوجی یال می‌توان یال‌ها را به مسیرهایی به طول ۲ افراز کرد. از تطابق کامل می‌توان برای توصیف یکی دیگر از خصوصیات گراف‌های پنجه‌آزاد استفاده کرد:

گراف‌هایی که هر زیرگراف القایی زوج رأسی همبند آن‌ها دارای تطابق کامل باشد، پنجه آزادند و برعکس.

نتیجهٔ قوی تر اثبات Sumner نشان می‌دهد که در هر گراف همبند پنجه آزاد دو رأس مجاور وجود دارند که با حذف آنها گراف همچنان همبند می‌ماند.

برای اثبات، Sumner دو رأس${\displaystyle v}$

ایدهٔ اثبات بالا برای وقتی که ${\displaystyle u}$