0
$\begingroup$

Let $G$ be a graph with no loops or cut edges. Show that $t(G)\geq e(G)$. Here, $t(G)$ is the number of spanning trees in $G$.

Here it says that the graph has no loops or cut edges this implies that the graph has no cut vertices and therefore there exist greater than or equal to $2$ many edge disjoint paths between any two vertices. The number of edges in each spanning tree is $n-1$ where $n$ is the number of vertices. I know the equality holds when the graph is $C_n$. Please help me with this. Thank you

$\endgroup$
1
  • 1
    $\begingroup$ If you mean $t(G)$ to count the number of trees that span $G$, you should say so in the body of the Question. $\endgroup$
    – hardmath
    Nov 3, 2021 at 22:04

1 Answer 1

1
$\begingroup$

Hint.

If $e$ is an arbitrary edge of graph $G$, then by condition graph $G-e$ is connected. Hence it has a spanning tree $T_e$. The same tree is a spanning tree for graph $G$. If $e'$ and $e''$ are different edges of graph $G$, then the trees $T_{e'}$ and $T_{e''}$ are different.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .