图论研究各种图的性质。图可以用来模拟现实世界中的许多情况，例如

社交网络的用户及其友谊关系；
一个国家中的城市以及连接它们的街道；
电信网络，如互联网和万维网；
语言结构，例如句子的句法结构；
项目管理，用于管理任务之间的依赖关系；
生物信息学：蛋白质-蛋白质相互作用、残基相互作用网络、基因调控；
数学关系，例如使用树的斐波那契展开；
决策树和贝叶斯网络；
电子电路：基尔霍夫定律与电路的图结构密切相关；
以及许多其他情况。

哥尼斯堡七桥问题

最著名也是最古老的现实世界问题是关于哥尼斯堡七桥问题。普鲁士的哥尼斯堡市（现为俄罗斯的加里宁格勒）位于普列戈尔河的两岸，包括两个大岛，它们通过七座桥相互连接并与大陆连接。

问题是找到一条穿过城市的路线，可以一次且仅一次地穿过每座桥。岛屿不能通过除桥梁以外的任何路线到达，并且每座桥都必须在每次通过时完全穿过；一个人不能走到桥上的一半，然后转身，然后从另一边穿过另一半。路线不必从同一个地方开始和结束。欧拉证明这个问题没有解决方案。不可能存在一条不重复的连续曲线穿过所有七座桥。困难在于开发一种分析技术和后续测试，以用数学的严谨性来确定这一断言。

首先，欧拉指出，在每个陆地上的路线选择无关紧要。路线的唯一重要特征是穿过的桥梁序列。这使他能够用抽象的术语重新表述问题（为图论奠定基础），消除了除陆地列表和连接它们的桥梁以外的所有特征。用现代术语来说，用抽象的“顶点”或节点替换每个陆地，用抽象的连接“边”替换每座桥，它仅用于记录哪对顶点（陆地）通过该桥连接。由此产生的数学结构称为图。

→ →

由于只有连接信息是相关的，图的图形表示的形状可以以任何方式扭曲，而不会改变图本身。每对节点之间是否存在（或不存在）边是重要的。例如，绘制的边是直线还是曲线，或者一个节点位于另一个节点的左侧还是右侧并不重要。

接下来，欧拉观察到（除路线的端点外），无论何时从桥进入顶点，都会从桥离开顶点。换句话说，在图中的任何路线中，进入非终端顶点的次数等于离开它的次数。现在，如果每座桥都只被穿过一次，则对于每个陆地（可能除了选择的起点和终点以外），接触该陆地的桥梁数量必须是偶数（在特定的遍历中，它们的一半将被“朝向”陆地遍历；另一半，则被“远离”它遍历）。然而，原始问题中的所有四个陆地都被奇数座桥接触（一个被 5 座桥接触，另外三个中的每一个被 3 座桥接触）。由于最多只有两个陆地可以作为假设路线的端点，因此遍历每座桥一次的命题会导致矛盾。

用现代语言来说，欧拉证明了穿过图的路线（只遍历每条边一次）的可能性取决于节点的度数。节点的度数是接触它的边的数量。欧拉的论点表明，所需形式路线的必要条件是图是连通的，并且只有一个或两个奇数度节点。这个条件也证明是充分的——这是一个由欧拉提出并后来由卡尔·希尔霍尔策证明的结果。这种路线现在被称为欧拉路径（oy•lɛr•i•ən）或欧拉路线，以纪念他。此外，如果有奇数度节点，则任何欧拉路径都将从其中一个节点开始，并在另一个节点结束。由于与历史上的哥尼斯堡相对应的图有四个奇数度节点，因此它不可能有欧拉路径。

问题的另一种形式要求一条遍历所有桥梁并且起点和终点相同的路径。这种路线称为欧拉回路或欧拉环游。这种回路存在当且仅当图是连通的，并且根本没有奇数度节点。所有欧拉回路也是欧拉路径，但并非所有欧拉路径都是欧拉回路。