图论
图论（graph theory）研究对象之间的连接关系。图中的点称为顶点，连接两个顶点的线称为边。例如把车站画成点、把相邻车站间的线路画成边，就可以研究能否到达、怎样经过所有线路以及如何选择路线。
图关注的是哪些点相连。把一条边画直或画弯，把两个相连顶点挪近或挪远，通常不会改变连接关系；若要表示路程或费用，则可以在边旁另标数值。
读懂一张五点图
下面的图有 A、B、C、D、E 五个顶点。先忽略边旁的数字，从 A 出发沿线观察：可以直接去 B 或 C；B、C 都能去 D；E 只与 D 相连。金色路线展示了从 A 经 B、D 到 E 的一种走法。
把顶点集合记为 V、边集合记为 E，就能将图写成 。本例为 这里 AB 与 BA 表示同一条边，它没有方向；同一对顶点间只画一条边，也没有顶点连回自身。这种图称为简单无向图。以下关于度数、树和二分图的讨论采用有限简单无向图。
如果道路只能单向通行，就在边上标箭头，得到有向图。如果两地之间的两座桥需要分别记录，就允许连接相同顶点的平行边，得到多重图。边旁有费用、长度等数值时，称为加权图，数值叫边权。道路在纸上交叉，只有明确标出连接顶点时才算路口。
度数：一共有多少个边端点
与顶点相接的边数，叫该顶点的度数，记作 。在图中，A 接 AB、AC，度数为 2；D 接 BD、CD、DE，度数为 3；E 的度数为 1。五个顶点的度数依次是 相加为 10，恰好是边数 5 的两倍。
这是握手定理： 左侧按顶点数边的端点，右侧按边数端点。每条无向边都有两个端点，因此每条边在总和中恰好被数两次。用握手比喻，一次握手既记入一个人的握手次数，也记入另一个人的次数。
总和是偶数。偶数度顶点的贡献本身为偶数，要使剩下的奇数度之和仍为偶数，奇数度顶点就必须有偶数个。本例恰有 D、E 两个。这条结论稍后会决定哪些顶点能成为走遍全部边的路线端点。若允许自环，一条自环的两个端点都在同一顶点，度数需计两次，握手等式才保持原意。
路径与连通：怎样从一个点走到另一个点
沿着边行走得到游走，顶点和边都可以重复。如果不重复任何边，称为迹；如果不重复任何顶点，称为路径。例如 是路径，而 重复经过 D，是迹而不是路径。
起点与终点相同、其他顶点不重复的闭合走法称为圈。简单无向图中的圈至少有三条边；本例的 是四条边组成的圈。
若任意两顶点之间都有路径，图就连通。本例连通，但删去 DE 后，E 与其余顶点分离。删掉这样的边会破坏连通性，称它为桥。相比之下，删去 CD 后仍可以沿 到达 D，图仍连通。
逐层寻找最少步数
从 A 去 E 最少要走几条边？先把 A 标为第 0 层；它的邻点 B、C 是第 1 层；从 B、C 继续走，首次发现 D，放在第 2 层；再从 D 发现 E，放在第 3 层。于是最少需要 3 条边。
这种逐层搜索叫广度优先搜索。每当发现一个新顶点，就记录从哪个顶点来到它；反向跟随这些记录，可以恢复一条最短路径。例如 E 从 D 发现，D 从 B 发现，B 从 A 发现，得到 。
逐层搜索之所以正确，是因为第 k 层的点已有长度 k 的路线。沿一条边首次到达的新点有长度 k+1 的路线；若它存在更短路线，那么在先前处理那条路线的前驱时就应已被发现。这样一层层推进，首次发现的层数恰好就是最少边数。
边权不同则是另一个问题。图中 与 都有三条边，但权重分别为 与 。金色路线的权重更小。处理不同边权的算法及负权情形见最短路径。
树：保留连接，去掉绕圈
删除图中的 CD 后，所有顶点仍能互相到达，却不再有圈。树就是非空、连通且无圈的无向图。
树中任意两点之间只有一条路径。连通性保证至少有一条；若有两条不同路径，从它们首次分开的位置出发，沿一条走到再次相遇处，再沿另一条返回，就会围成一个圈。因此路径不能有两条。
含 n 个顶点的有限树恰有 条边。证明可以从“叶子”入手：叶子是度数为 1 的顶点。一棵至少有两个顶点的有限树必有叶子，因为选一条最长路径，它的端点不能再接路径外的点，否则还能延长；也不能接路径中除相邻点外的点，否则产生圈。因此最长路径的两端都是叶子。
删去一个叶子及其唯一相接的边，其余部分仍连通且无圈。每次顶点和边都各少一个，反复删到只剩一个顶点、零条边，便得到原来边数始终比顶点数少 1。本例删去 CD 后有 5 个顶点、4 条边，正好符合公式。
反过来，有限 n 顶点图若连通且有 n−1 条边，也必为树。若它有圈，可以从圈上删一条边而保持连通；不断这样删，最终得到含全部顶点的一棵树，已经需要 n−1 条边。原来只有这么多边，就没有可删的多余边。只有边数而没有连通条件不够：三角形外加一个孤立点有 4 个顶点、3 条边，却不是树。
每条边恰走一次：欧拉迹
回到未删边的原图。现在不求最快到达，而要使五条边恰好各经过一次。路线 正好依次经过 DB、BA、AC、CD、DE，每条一次。这样的迹称为欧拉迹；若最后回到起点，称为欧拉回路。
下面把这条走法按 1 到 5 标出。箭头只记录本次行走方向，原图的边仍是无向边；边旁数字现在是经过次序，不是前图的费用。沿箭头走完，D 虽被再次经过，每条边却都恰好使用一次。
起点为何选 D，终点为何选 E？沿路线经过一个中途顶点时，每次进入都要配一次离开，因此所用的边成对出现。走完全部边后，中途顶点的度数为偶数；开放路线的起点和终点各多一次离开或进入，度数为奇数。因此一条欧拉迹若不闭合，两个端点恰好就是两个奇数度顶点。
完整判据为：有限无向图至少有一条边，且所有非孤立顶点相互连通时，有欧拉迹当且仅当奇数度顶点有 0 个或 2 个。零个时可以闭合，两个时必须以这两点为端点。
为什么奇偶条件也足以构造路线
先设所有度数都为偶数。从一个有边的顶点出发，每次选择尚未使用的边，直到无法继续。若走到起点以外的某点，先前每次进入和离开都成对，当前这次进入又使用了一条边；既然总度数为偶数，就还会剩下一条未用边可以离开。因此走法不会停在其他点，只能回到起点，形成一条闭合迹。
若还有边没用，由连通性，当前闭合迹上必有某点与未用边相接。从这个点再次沿未用边行走：已用的闭合迹在每点消耗偶数条边，剩下的度数仍为偶数，故又能得到一条闭合迹。将它插入原迹，再继续处理剩余边。边数有限，这个过程最终用完全部边。
若只有两个奇数度顶点，先在它们之间加一条临时边，使度数都变偶数，构造欧拉回路后去掉临时边，即得到所需开放迹。原来已有连接边时，临时边与它平行，需要将两条边分别识别；上述配对论证同样适用于这种多重图。
若在配图中再加 BE，B 的度数从 2 变 3，E 从 1 变 2，D 仍为 3。新图仍有欧拉迹，但两个端点改成 B、D。A 为偶数度，不能作为这种开放迹的起点。
哈密顿路径则要求每个顶点恰好经过一次，不要求用完所有边。例如 是本例的一条哈密顿路径。两种“走遍”分别约束边和顶点，问题不同。
把顶点分成两组：二分图
将配图顶点分为 与 。检查每条边，AB、AC、BD、CD、DE 都跨越两组，没有边连接同组内的两个点。能够这样分组的图叫二分图。
二分图中的圈只能有偶数条边：每走一步都会换到另一组，回到原来一组必须走偶数步。因此三角形无法二分。反过来，有限无向图只要没有奇数长度的圈，就能分成两组。
可以用广度优先搜索证明反向结论。对每个连通部分选一个起点，把距离为偶数的顶点放一组，奇数的放另一组。若有一条边连接同组两点，它们在搜索树中的深度同奇偶。从一端沿树走到两条根路径最后的共同点，再走到另一端，这条树路径长度为“两端深度之和减去共同深度的两倍”，所以为偶数。加上这条连接边，就围成奇圈，与假设矛盾。因此所有边都跨组。
本例从 A 搜索，偶数层为 A、D，奇数层为 B、C、E，正得到前面的划分。若图不连通，对每个尚未访问的部分分别开始搜索即可。
二分性看圈的长度，欧拉迹看顶点的度数，两者不同。三角形每点度数为 2，有欧拉回路，却不是二分图；一个中心连接三个叶子的星形树可以二分，却有四个奇数度顶点，没有欧拉迹。
怎样记录同一张图
按 A、B、C、D、E 排列顶点，用 1 表示相邻、0 表示不相邻，可以写出邻接矩阵： 例如第一行在 B、C 两列为 1，记录 A 的两个邻点。无向性使矩阵对称，没有自环使对角线为零。
矩阵乘法还可以数两步游走。 中，每个中间顶点 k 对应一条“先从 i 到 k，再从 k 到 j”的可能走法。例如 A 到 D 可以经过 B 或 C，所以对应元素为 2。
也可以只给每个顶点列出邻点，称为邻接表。搜索时每个顶点只需首次发现时入队，每条无向边从两端各检查一次，因此广度优先搜索的时间量级为 。
若给顶点改名或重画位置，却能一一对应地保留相邻关系，两张图称为同构。相同度数序列还不足以证明同构：六边形圈与两个分开的三角形都有 6 个顶点、6 条边，每点度数均为 2，但前者连通，后者不连通。
历史
欧拉研究柯尼斯堡七桥问题时，以陆地区域和桥的连接替代具体的地理形状。能否每座桥恰过一次，取决于连接和度数，而不是桥的实际长度。原论文收录于 Euler Archive，E53，档案标示撰写时间为 1735 年、出版时间为 1741 年。
这一问题是图论早期发展的重要例子。此后，地图着色、化学分子结构、组合计数及计算机网络等问题不断扩展图论的研究范围。MacTutor 的历史综述介绍了七桥问题与拓扑观念发展的联系。