فرض کنید $G_1, G_2$ دو گراف ساده‌ی برچسب‌دار با مجموعه‌ی رئوس $\{v_1, v_2, \ldots, v_n\}$ باشند. تفاضل متقارن این دو گراف را که با $G_1 \Delta G_2$ نشان می‌دهیم، گرافی با مجموعه‌ی رئوس $\{v_1, v_2, \ldots, v_n\}$ است که یال $v_iv_j$ در آن می‌آید، اگر و تنها اگر در دقیقن یکی از $G_1, G_2$ آمده باشد.

حال گراف ساده‌ی برچسب‌دار $G$ با مجموعه‌ی رئوس $\{v_1, v_2, \ldots, v_n\}$ را در نظر بگیرید. به ازای هر یک از $n!$ گراف ممکن که از جایگشت دادن این برچسب‌ها روی رئوس به دست می‌آید، تفاضل متقارن گراف مذکور را با $G$ حساب کرده و اگر گراف حاصل تهی نبود، آن را در مجموعه‌ی $D(G)$ می‌گذاریم. به گراف $G$ سلطانی گوییم، هر گاه اعضای $D(G)$ دوبه‌دو یک‌ریخت باشند.

فرض کنید $n > 6$ یک عدد طبیعی است. ثابت کنید یک گراف ساده‌ی $n$ رأسی سلطانی است، اگر و تنها اگر گراف کامل، گراف تهی، ستاره یا مکمّل ستاره باشد.

• سوال قبل