It looks like there wasn't really a common belief; see the question What was the origin of the Seven Bridges of Königsberg problem before Euler?.
The answer by user @Conifold quotes researcher Teo Paloetti:
According to lore, the citizens of Königsberg used to spend Sunday afternoons walking around their beautiful city. While walking, the people of the city decided to create a game for themselves, their goal being to devise a way in which they could walk around the city, crossing each of the seven bridges only once. Even though none of the citizens of Königsberg could invent a route that would allow them to cross each of the bridges only once, still they could not prove that it was impossible.
and Euler himself:
The problem, which I am told is widely known, is as follows: in Königsberg in Prussia, there is an island A called the Kneiphof; the river which surrounds it is divided into two branches, as can be seen in Fig. [1.2], and these branches are crossed by seven bridges, a, b, c, d, e, f and g. Concerning these bridges it was asked whether anyone could arrange a route in such a way that he would cross each bridge once and only once. I was told that some people asserted that this was impossible, while others were in doubt; but nobody would actually assert that it could be done. From this, I have formulated the general problem: whatever be the arrangement and division of the river into branches, and however many bridges there be, can one find out whether or not it is possible to cross each bridge exactly once?