گراف حاصل تلاش و کوشش لئونارد اویلر ریاضیدان سوئیسی برای حل یکی از مساله های معروف زمان خود بود که در نهایت منجر به پیدایش مفهوم گراف گردید. و مساله ای که اویلر روی آن کار کرد به مساله پل های کونیسیرگ شهرت دارد. از وسط شهر کونیگسبرگ رودخانه ای می گذرد که دو جزیره را در برگرفته است . در آن زمان بین ساحل رودخانه و جزیره ها 7 پل وجود داشت.
مساله این بود که شخصی از هر یک از نواحی A ، B ، Cو یا D حرکت کند و از هر یک از پل ها یک بار و فقط یک بار بگذزرد و به نقطه شروع بازگردد. اهالی شهر در هنگام گردش وپیاده روی می کوشیدند مساله را عملا حل کنند. ولی کوشش آن ها بی نتیجه می ماند. تا این که اویلر با باداع نظریه ای که در آن هندسه بدون اندازه نامید توانست حل ناپذیری آن را ثابت کند. اویلر ابتدا مدلی ریاضی برای مساله درست کرد : به هر یک از جزیره ها و ساحل ها یک نقطه نسبت داد و دو نقطه متناظر با دو ناحیه ای را که با پلی مرتبط بودند با پاره خط یا کمانی به هم وصل کرد.
با این کار اویلر یک گراف به دست آورد.اویلر در مقاله بسیار کوتاهی با استدلالی ساده عبث بودن کوشش ها را ثابت کرد. لازم به ذکر است که هر چند ریشه های نظریه گراف ها به اواسط قرن هجدهم میلادی برمی گردد ولی شناخت زیبایی و کارایی در زمینه های نظری و علمی تا نیمه قرن بیستم میلادی به درازا کشید.