Thread by @ccanonne_

📊 Today, (weakly|weekly) quiz will be about graphs. The ones with nodes and edges, not those plotting against you.

Specifically, *planar* graphs. The nice ones.

1/7

What's an (undirected) graph here? Just a pair G=(V,E) of n=|V| vertices (nodes) and m=|E| edges, where E ⊆ V×V and each edge in E is a pair (v₁,v₂) indicating if the two nodes v₁ and v₂ are connected.
If E=V×V (all possible edges), G is the complete graph, Kₙ.

2/7

(above, that's K₇, also very cool on t-shirts.). A graph G is *planar* if you can draw it on a sheet of paper w/o crossing edges ("can be embedded in the plane"). Kₙ, for instance, is not planar.

Leading us to Q1: I give you G. How hard is it to decide if it's planar?

3/7

Nice. So, let's say G is a planar graph, with n nodes and m edges (and connected: any 2 nodes can be linked by a path made of edges). You draw it on a sheet of paper, and doing so you divide the sheet into a bunch of disjoint areas.

Q2: How many areas do you have?

4/7

Final question! You have your planar graph G, but you'd like to apply some recursive algorithm, or feel sort of playful, and want to divide it in two "balanced" subgraphs G₁,G₂ almost disjoint.

Specifically, you'd like both G₁ and G₂ to have at least n/3 vertices each.

5/7

Now, to do that you may need to first remove a few nodes from G=(V,E), say t of them, and after that the remaining n-t nodes can be divided in two balanced sets V₁ and V₂ such that there is no edge in E going b/w V₁ and V₂.

Q3: how many nodes, t, do you have to remove?

6/7

That's all for today! Answers and discussions tomorrow, as usual. Please feel free to comment/ask questions below in the meantime... ↯

7/end