Now on

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


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

  1. Pingback: The curious powers of 1 + sqrt 2 | The Math Less Traveled

  2. David Acer says:

    A tree-mendous proof!

  3. Pingback: Twitter, but for Math, with Toots | Artificia Intelligence

Comments are closed.