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 · 0 · 1 · 4

@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.

Sign in to participate in the conversation

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