树与生成树
无向图若连通且不含环，称为树（tree）。连通保证任意两点间至少有路，无环保证至多有一条简单路；两项合在一起，树中任意两点之间恰有一条简单路。树的边不能再删，否则会断开；在任意两点间再添一条新边，则会与原有唯一路径合成一个环。
边数为顶点数减一
一棵有 个顶点的有限树恰有 条边。可用归纳证明：一棵非单点树至少有一片叶子（度数为 1 的顶点）；删去叶子及其唯一边，剩余图仍连通且无环，是 个顶点的树。按归纳假设它有 条边，加回被删的一条，得到 。初始的单点树有零条边，公式也成立。
从连通图取得生成树
生成树保留原图全部顶点，只挑选其中的部分边，使它们构成一棵树。若原图连通且含环，删去环上的任一边仍连通：原先使用这条边的路径可沿环的另一侧绕行。重复删环，最终得到生成树。例如一个四边形再加一条对角线共有 5 条边；任取保持四点连通且无环的 3 条边就是生成树。
生成树只记录“怎样把所有点接起来”，不要求经过原图每条边。最小生成树还要求边权总和最小，须先给出边权；普通生成树没有这个优化条件。图论中的搜索树可帮助记录遍历，但搜索顺序不同可能得到不同生成树。