Утверждение. В связном неориентированном графе с $n$ вершинами и $n$ рёбрами существует ровно один простой цикл.
Доказательство (через остовное дерево). Пусть $G$ — связный граф с $n$ вершинами и $m=n$ рёбрами. Возьмём любое остовное дерево $T\subset G$. Для связного графа остовное дерево имеет ровно $n-1$ рёбер. Значит в $G$ ровно одно ребро лежит вне $T$:
$$|E(G)\setminus E(T)|=m-(n-1)=n-(n-1)=1.$$ Обозначим это ребро $e=uv$. В дереве $T$ между $u$ и $v$ существует единственный простой путь $P_T(u,v)$. Добавление ребра $e$ к $T$ даёт цикл $C=P_T(u,v)\cup \{e\}$. Это простой цикл и он существует. Обратно, никакой другой простой цикл не может лежать в $T$ (т.к. $T$ ациклично), значит любой цикл в $G$ обязан содержать хотя бы одно ребро из $E(G)\setminus E(T)$. Но таких рёбер ровно одно — $e$ — поэтому все циклы содержат $e$ и, так как в $T$ путь между концами $e$ единственен, единственный простой цикл в $G$ — это $C$. Таким образом ровно один простой цикл.
Связь с цикломатическим числом. Цикломатическое число (dimension of cycle space) для произвольного графа с $m$ рёбрами, $n$ вершинами и $c$ компонентами равно
$$\mu =m-n+c.$$ Для связного графа $c=1$, поэтому
$$\mu =m-n+1.$$ При $m=n$ получаем $\mu =1$, что согласуется с доказанным фактом: размер пространства циклов равен 1 (ровно одна независимая циклическая структура).
Обобщение. Если связный граф имеет $n+k$ рёбер ($m=n+k$), то
$$\mu =m-n+1=(n+k)-n+1=k+1.$$ Эквивалентно: выбрав остовное дерево $T$ (с $n-1$ рёбрами), в графе останется ровно $m-(n-1)=k+1$ рёбер вне $T$; каждое такое ребро порождает фундаментальный цикл относительно $T$, и эти $k+1$ фундаментальных циклов образуют базис пространства циклов (то есть ровно $k+1$ независимых циклов).