Let $$G$$ be a graph with $$|V|=n$$. Any two of the following imply the third: 1. $$G$$ is connected; 2. $$G$$ is acyclic; 3. $$G$$ has $$n-1$$ edges.

1,2 => 3: by induction. Any walk must reach a leaf. Delete it and apply the IH.

1,3 => 2: by induction. Sum of degrees is $$2(n-1)$$, so there are at least two leaves. Delete one and apply the IH.

2,3 => 1: Let $$G$$ have $$c$$ connected components. Since 1,2 => 3 for each, the total number of edges is $$n-c$$, hence $$c=1$$.

· · Web · · ·

@byorgey A refinement to this could use the fact that Euler characteristic equals both $$n-e$$, where $$e$$ is the number of edges, and $$b_0-b_1$$, where $$b_0$$ is the number of connected components and $$b_1$$ the dimension of cycle space. If $$G$$ is connected then $$b_0=1$$ so $$n-e=1-b_1$$, which means $$e=n-1$$ is equivalent to $$b_1=0$$ (aka $$G$$ is acyclic). If $$G$$ is acyclic then $$e=n-b_0$$. If $$e=n-1$$, then $$b_0=1+b_1$$.

@kmill That's a nice proof, though it does rely on first proving those facts about Euler characteristic. I was trying to produce something relatively self-contained.

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!