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.

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:

WordPress.com Logo

You are commenting using your WordPress.com 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