گراف پترسن گرافی غیر جهت دار، با ۱۰ راس و ۱۵ یال است. این گراف، گرافی کوچک می‌باشد که به عنوان مثالی مفید و همچنین مثال نقض در بسیاری از مسائل نظریه گراف به کار می‌رود. یولیوس پترسن[۱](۱۸۳۹-۱۹۱۰) دانشمندی دانمارکی بود که در سال ۱۸۹۸ گرافی را، که به نام خودش ثبت شد، به عنوان کوچکترین گراف مکعبی (گرافی که هر راس آن از درجه ۳ باشد.) بدون پل ساخت. در واقع این گراف مثال نقضی برای این ادعا بود که یک گراف مکعبی بدون پل متصل، داری یک رنگ آمیزی یالی با ۳ رنگ است. در حالی که این گراف دارای این رنگ آمیزی با ۴ رنگ می‌باشد. با این که این گراف به‌طور عمومی به یولیوس پترسن نسبت داده می‌شود، ولی درحقیقت برای اولین بار ۱۲ سال زودتر از ساختن آن توسط وی، در سال ۱۸۸۶ به وجود آمده بود. دونالد نوث[۲] اذعان می‌کند که گراف پترسن، شکل و پیکری قابل توجه‌است که به عنوان مثالی نقض برای بسیاری از اسناد و اثبات‌های خوش بینانه دربارهٔ این که چه چیزهایی ممکن است به‌طور عمومی برای گراف‌ها درست باشد، به کار می‌رود. https://eitaa.com/mathteaching