Definition

图中的边是连接两个顶点的一条线，表示这两个事物之间的关系；边可以携带额外信息，加权边可能表示距离或成本，而有向边（箭头）表示单向关系。严格地说，边 $\{u, v\}$（无向）或 $(u, v)$（有向）连接顶点 $u$ 和 $v$，加权图为每条边赋予一个数值权重 $w(e)$，简单图没有自环，也没有连接同一对顶点的多条边。在正式的边集表示法中，对于简单无向图，$E \subseteq \{\{u,v\}: u,v \in V, u \neq v\}$；边连通度 $\lambda(G)$ 是使 $G$ 断开连通所需移除的最少边数，由门格尔定理，它等于任意两个顶点之间边不相交路径的最大数目。