Koenigsberg Bridge Problem

Author

Eric W. Weisstein
August 23, 2021

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/KoenigsbergBridgeProblem.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/KoenigsbergBridgeProblem.html.

©2021 Wolfram Research, Inc. except for portions noted otherwise

Original bridge configuration

V5

KoenigsbergBridges=SetVertexLabels[ChangeVertices[AddEdges[EmptyGraph[4],{{1,3},{1,2},{1,2},{2,3},{2,4},{2,4},{3,4}}],{{0,1},{0,0},{.5,0},{0,-1}}],
StyleForm[#,FontFamily->"Times",FontSlant->"Italic",Background->White]&/@{"C","A","D","B"}]

ShowGraph[KoenigsbergBridges]

Through[{V,M}[KoenigsbergBridges]]

EulerianQ[KoenigsbergBridges]

V12

g1=Graph[{"A","B","C","D"},UndirectedEdge@@@{{"A","B"},{"A","B"},{"A","C"},{"A","C"},{"A","D"},{"B","D"},{"C","D"}},VertexCoordinates->{{0,0},{0,-1},{0,1},{Sqrt[3],0}},VertexLabels->Automatic]

EulerianGraphQ[g1]

New bridge configuration

V5

NewKoenigsbergBridges=SetVertexLabels[ChangeVertices[AddEdges[MakeDirected[EmptyGraph[4]],Partition[{3,4,1,3,2},2,1]],{{0,1},{.05,0},{.5,0},{0,-1}}],StyleForm[#,FontFamily->"Times",FontSlant->"Italic",Background->White]&/@{"C","A","D","B"}]

ShowGraph[NewKoenigsbergBridges,PlotRange->All]

ShowGraph[MakeUndirected[NewKoenigsbergBridges]]

EulerianQ[MakeUndirected[NewKoenigsbergBridges]]

V12

g2=Graph[{"A","B","C","D"},DirectedEdge@@@{{"D","A"},{"C","D"},{"B","C"},{"D","B"}},VertexCoordinates->{{1/4,0},{0,-1},{0,1},{Sqrt[3],0}},VertexLabels->Automatic]