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

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s