مسئله پلهای کونیگسبرگ یکی از مشهورترین مسایل در نظریه گراف است که در مکان و شرایط واقعی طرح شدهاست. در اوایل سده ۱۸ ساکنین کونیگسبرگ در پروسیا (در حال حاضر کالینینگراد در روسیه) در روزهای یکشنبه به پیادهرویهایی طولانی در شهر میرفتند. رود پرگولیا شهر را به چهار قسمت تقسیم میکرد که با هفت پل به هم مرتبط بودند. ساکنان سعی میکردند مسیری بیابند که پیادهروی را از نقطهای در شهر شروع کنند و از تمامی پلها فقط یکبار بگذرند و دوباره به نقطه شروع بازگردند.
