The Greatest Common Denominator


Dear Nobody,

The reader unconcerned with proof techniques or elementary graph theory should skip straight to the concluding theorem or more likely its subsequent corollary. I am convinced that this includes most potential readers of this note.

Definitions. A connected component is a subgraph for which every vertex is connected by a path of edges to every other vertex. A line is a connected component that is itself a line graph, which is a graph composed of a single path of edges between vertices. A circuit is generally a closed path of vertices connected in a loop, with each vertex occurring only once, but here refers to a connected component consisting only of a general circuit.

Let G = (V,E) be a simple graph. Let M1, M2 be two matchings of G. Let G’ = (V, M1 U M2)

Lemma 1. G’ consists exclusively of isolated vertices and connected components with 0 or more vertices of degree 2 and strictly 0 or 2 vertices of degree 1. That is, each connected component is an isolated vertex, a line, or a cycle.

Proof. By cases. Because, in either matching in G, each vertex has degree at most 1, each vertex in G’ has degree at most 2. This implies that each connected component is an isolated vertex, a line, or a cycle. To prove this implication, assume that each vertex in G’ has degree at most 2. Then no vertex is a branching point, which would have degree greater than 2, so each vertex continues or stops a path or cycle, or is isolated. These cases are divided into the following two.

Case 1: The connected component contains a vertex of degree 0. That vertex is connected to no other vertex, so the connected component is an isolated vertex. The implication is true for this case.

Case 2: The connected component contains no vertex of degree 0. There are two subcases.

Case 2a: The connected component contains a vertex of degree 1. The path stops at the vertex, and must stop at the other end, as a cycle now requires a branching point to which to loop back. There are two vertices of degree 1 in the connected component, and any remaining vertices have degree 2—the component is a line. The implication is true for this subcase.

Case 2b: The connected component contains no vertex of degree 1. There are only degree 2 vertices, so the connected component has no endpoints, and must form a cycle*. The implication is true for this subcase.

The implication holds in all cases—the lemma is proved.

* I assume a graph with only finite connected components, but connected components with infinite vertices are infinite lines with 0 or 1 endpoints, the infinite lines are bipartite for the reasons presented below in lemma 3, and the theorem itself holds.

Lemma 2. If a connected component in G’ is a cycle, then it has an even number of vertices.

Proof. Assume a connected component in G’ is a cycle. Then every vertex has degree 2, and so was matched in both M1 and M2, with a different vertex in each matching. Because in the individual matches, the vertices form pairs, any group of individual matches must have an even number of vertices. Further, any match appearing in both M1 and M2 results in two vertices of degree 1, so there are no cases of doubly counted vertices in an individual cycle in G’—in each matching, the vertices contributing to the cycle are in pairs, so in their union there remains an even number of vertices.

Lemma 3. If a connected component is a line, then it is bipartite.

Proof. Assume a connected component is a line. Then its vertices can be numbered sequentially so that even-numbered vertices connect only to odd-numbered vertices, and the line can be partitioned into L and R by parity. It is thus bipartite.

Corollary. If a connected component is a cycle with an even number of vertices, it is bipartite.

Proof. Assume a connected component is a cycle. A cycle can be considered a line with a final edge between its last vertex and its first. Partitioned as the line in lemma 3, if the final vertex is even-numbered, and the edge connects it to the first, which is odd-numbered, the edge is between L and R and the cycle remains bipartite.

Theorem. G’ is bipartite.

Proof. By lemmas 1 and 2, the connected components of G’ are exclusively individual vertices, lines, and cycles with an even number of vertices. By lemma 3 and its corollary, in G’ each connected component that contains an edge is bipartite. Every edge is contained in a bipartite connected component if and only if the entire graph is bipartite, as the partitions can be gathered arbitrarily between connected components into partitions L and R (and a bipartite graph may be divided into bipartite components). The theorem is proved.

Corollary. It would be super rad if Kim would rob banks with me.

The proof is left as an exercise.

Yours Truly,

The World’s Greatest Genius

P.S. I was getting mad on how people keep saying I can’t play instruments, so last night I learned every instrument and wrote a kind of weird opera thing by accident.

P.P.S. I’ma crumple these napkins, but some Nobody’s sure to dig them out of the diner trash. Sometimes I wish I didn’t have the world’s most famous face. Then we really could rob banks.

P.P.P.S. Stay quiet about the bank robbing, you stupid Nobody.


The police detective studied the napkins. He kept squinting and pushing his reading glasses up. An upset man sat across from him. The detective perused the napkins for a long time, then set them down, looked to the ceiling and waved his hands. He turned his attention to the crying man.

“Of course it’s very elementary graph theory,” said the detective. “There’s more advanced work on all of his albums.”

“Yes,” said the man. “That’s not what bothers me.”

“If you’re familiar with his work, you should know that he’s always wanted to rob banks.”

“Bonnie and Clyde stuff, yes,” said the man.

“What’s bothering you?”

“He called me stupid.”

Advertisements

Leave a Reply

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