有限简单无向图

图把对象内部结构暂时折叠，只留下“哪两者直接相连”。一条边只表达一次成对关系，不说明关系为何出现、强度多大，也不提供从一个端点到另一个端点的优先方向。这样的抽象让同一套语言能够研究交通换乘、通信链路和资源冲突，同时也要求建模者明确哪些信息被有意丢弃。

局部统计无法恢复整张图。度数告诉我们每个顶点有多少邻点，却不说明这些邻点怎样彼此连接；路径、分量、圈和团都取决于边的全局编排。研究图结构，因而既要看顶点周围的局部形状，也要追踪局部形状如何拼成整体。

把图画在纸上只是表示它的一种方式。移动顶点、弯曲边或交换标签，只要相邻关系不变，数学对象就没有改变。邻接表、邻接矩阵和边列表同样只是编码；它们会改变查询与遍历成本，不会改变 $G=(V,E)$ 本身。

城市地铁的换乘骨架可以把车站视为顶点，把“有一段线路直接连接”视为边。若两个车站之间有多条不同线路，简单图会把它们压成一条边；若还要记录行车时间，需要权函数；若上下行可用性不同，则应改用有向模型。模型是否合适，取决于问题是否需要这些被压掉的信息。

六个顶点组成的圈 $C_6$ 与两个互不相交的三角形具有同一个度数序列

但前者连通，后者有两个连通分量。这个例子直接显示：即使顶点数、边数和每个顶点的度数完全一致，图仍可能具有不同的全局结构。

当 $V=\varnothing$ 时只能有 $E=\varnothing$，得到零阶图；当 $|V|=1$ 时也没有可选边。二者都满足形式定义，但“空图是否连通”等后继性质常有不同约定，使用时需要查看对应条目的量词范围。

自环 $\{v,v\}$ 不是二元子集，平行边也不能在集合 $E$ 中保留两份。若任务确实区分重复道路、重复交易或自反馈，应该直接使用多重图或允许自环的模型，而不能在简单图中暗中塞入额外身份。

从 $G$ 删除部分顶点或边得到子图公理库子图Subgraph从母图删除顶点或边、同时保留剩余边端点关系所得的图。；沿边把局部相邻串起来得到路与圈公理库路与圈Path and cycle in a graph用相邻顶点序列刻画图中的行走、简单路径与首尾闭合的简单圈。；可达性进一步把顶点划成连通分量公理库图连通性Graph connectivity用顶点间是否存在路径定义无向图的连通性，并由此划分连通分量。。这些概念都只读取同一对集合 $V,E$，却回答不同层次的问题。

图上的约束通常选取顶点或边的特殊子集。匹配公理库匹配Matching in a graph由彼此不共享端点的边组成、表达一对一配对约束的边集合。要求所选边没有公共端点，团与独立集公理库团与独立集Clique · Independent set · 团 · 独立集顶点集内部的边关系分别达到两两全有与两两全无时形成的两类结构。分别要求所选顶点两两相邻或两两不相邻，图染色公理库图染色Graph coloring · Vertex coloring为图的顶点赋予颜色并要求每条边的两个端点颜色不同的可行标记。则把顶点分成若干独立颜色类。它们共享输入骨架，证书与优化目标并不相同。

有限性只保证对象规模有限，不保证输入能以常数时间随机访问。邻接矩阵用 $\mathrm{\Theta }(n^2)$ 空间换取快速相邻查询；邻接表用 $\mathrm{\Theta }(n+m)$ 空间贴近稀疏图；若边以数据流到达或持续插删，还要另外规定访问与更新协议。复杂度结论只有在表示模型明确之后才有可比性。