Primeiro, Euler apontou que a escolha da rota dentro de cada massa terrestre não importa. A única propriedade importante de uma rota é a ordem na qual as pontes são atravessadas. Portanto, ele mudou o problema para termos abstratos. Isto lançou as bases da teoria dos gráficos. Ele removeu todas as características, exceto a lista das massas de terra e as pontes que as ligavam. Na linguagem da teoria gráfica, ele substituiu cada massa de terra por um "vértice" ou nó abstrato. Depois ele substituiu cada ponte por uma conexão abstrata, uma "borda". Uma borda (estrada) registrou quais dois vértices (massas de terra) estavam conectados. Desta forma, ele formou um gráfico.
→ → 
O gráfico desenhado é uma imagem abstrata do problema. Portanto, as bordas podem ser unidas de qualquer maneira. Somente se dois pontos estão conectados ou não são importantes. Mudar a imagem do gráfico não muda o gráfico em si.
Em seguida, Euler observou que (exceto nos pontos finais da caminhada), sempre que se entra num vértice por uma ponte, sai-se do vértice por uma ponte. Em qualquer caminhada do gráfico, o número de vezes que se entra em um vértice é igual ao número de vezes que se sai dele. Se cada ponte foi atravessada exatamente uma vez, segue-se que, para cada massa terrestre (exceto para as escolhidas para o início e o fim), o número de pontes que tocam essa massa terrestre deve ser uniforme. Isto porque, se houver n pontes, ela é atravessada exatamente 2n vezes. Entretanto, todas as quatro massas de terra do problema original são tocadas por um número ímpar de pontes (uma é tocada por 5 pontes, e cada uma das outras três é tocada por 3). Há no máximo duas massas que podem ser os pontos finais de uma caminhada. Portanto, a proposta de uma caminhada que atravessa cada ponte uma vez leva a uma contradição.
Em linguagem moderna, Euler mostra que a possibilidade ou não de um passeio através de um gráfico cruzando cada borda uma vez depende dos graus dos nós. O grau de um nó é o número de arestas que o tocam. Euler mostra que uma condição necessária para a caminhada é que o gráfico esteja conectado e tenha exatamente zero ou dois nós de grau ímpar. Este resultado declarado por Euler foi provado mais tarde por Carl Hierholzer. Tal caminhada é agora chamada de caminho Euler ou caminhada Euler. Se houver nós de grau ímpar, então qualquer caminho Euleriano começará em um deles e terminará no outro. Como o gráfico que representa o histórico Königsberg tem quatro nós de grau ímpar, ele não pode ter um caminho Euleriano.
O trabalho de Euler foi apresentado à Academia de São Petersburgo em 26 de agosto de 1735. Foi publicado como Solutio problematis ad geometriam situs pertinentis (A solução de um problema relativo à geometria da posição) na revista Commentarii academiae scientiarum Petropolitanae, em 1741. Está disponível em inglês no The World of Mathematics.
