## Now on mathstodon.xyz

Christian Lawson-Perfect and Colin Wright have set up an instance of Mastodon—a decentralized, open-source Twitter clone—as a place for mathy folks to be social. It’s appropriately named mathstodon.xyz, and because it’s open-source they were able to easily hack in $\LaTeX$ support. Neato! I’ve never been on Twitter—the costs of the resulting distraction would far outweight any benefits for me—but mathstodon.xyz seems like it could be a fun place to discuss math without being endlessly distracting (we’ll see), so I decided to try it out for now: I’m `@byorgey`.

Here’s my initial entry to the `#proofinatoot` contest—the idea is to write a proof that fits in Mastodon’s 500-character limit for “toots” (you know, like a tweet, but more mastodon-y). To fit this proof into 500 characters I had to leave out a lot of details; it was a fun exercise to take a cool proof and try to distill it down to just its core ideas. Can you fill in the details I omitted? (Also, can you figure out what word is commonly used to refer to graphs with these properties?)

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 \Rightarrow 3$: by induction. Any walk must reach a leaf. Delete it and apply the IH.

$1,3 \Rightarrow 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 \Rightarrow 1$: Let $G$ have $c$ connected components. Since $1,2 \Rightarrow 3$ for each, the total number of edges is $n-c$, hence $c=1$.

Advertisements

## About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in meta, proof and tagged , , , , , , . Bookmark the permalink.

### 3 Responses to Now on mathstodon.xyz

1. David Acer says:

A tree-mendous proof!

Comments are closed.