How to draw two-part graphs

Graphic love

Last night Rike had a nightmare: She is walking on a ridge in a huge mountain range, deep gorges to the right and left. Then she falls to one side and wakes up. She worries, she is lovesick. She heard that Max fell in love with purple. Now she's thinking about flying to Calcutta to spend a few nice days with Max. But if she flies to Max, Ben will resent her. She has the feeling that she has to finally turn to one side and thus have to make a decision.

Now she takes a piece of paper and writes down the relationship situation graphically. When two people come together, love each other and split up, it looks like this graphically:

Relationship graphs

But with her it's more complicated, it's not just 2 people, but 4. She met Max a long time ago and is his girlfriend. Then Ben and Lila joined them. Now she is with Ben, and Max with Lila. If she flies to Calcutta, maybe she'll get back together with Max?

 

In addition to the sadness about Max ‘new love, she also has hope. Hm, a nice planar graph, she thinks. But what happens when she flies to Calcutta with Ben, gets back together with Max and when Ben falls in love with Lila? Then she needs another dimension to draw that:

 

Now the graph is no longer planar, she doesn't know what to do next. Nobody here in Bielefeld knows what to do next. She'll have to call her friend Anna in Berlin.

Rike Hi Anna. I have such a damn graph, it's not planar. Wait, I'll send it to you. Here! Do you know what characteristics it has? How can i draw it?

Kuratowski's theorem

Anna Hi, Rike, are you not feeling so well? I'll try. If the graph is really not planar then it must either be the graph or the contain. One is a complete graph with 5 vertices, the other is a two-part, complete, so-called graph bipartite. That is Kuratowski's theorem.

Rike Oh, I think the two are not in.

Anna Can't you fold up one of the two parts that go down?

Rike That's right, I wanted to draw the graph like in phase space, I thought the arrow represents time and always goes down.

Anna No, you don't need that. A graph is not a phase space. The vertices are not the states.

Rike That's right, for me the edges are the states and the vertices represent changes of state. Then I fold up a branch and the planar graph over the 4-way relationship is done.

Euler characteristic

Anna Have you already determined the Euler characteristic?

Rike How does it work? I thought it’s only available for polyhedra?

Anna No, they are also available for graphs. You cut a polyhedron at one edge, unfold it and interpret the vertices and edges as those of a graph. When counting the areas, add the outer one. The Euler characteristic is an invariant for every graph

V… number of vertices / nodes
E… number of edges
F… number of faces including the outer one

Every planar, connected graph has the characteristic 2.

Rike Okay on this graph is

and consequently

The Euler characteristic is correct. That’s just nice.

Anna Can I still do something for you?

Rike Thanks, that's it for now. Give my regards to David!

***

Exercises

  1. Prove the Euler characteristic.
  2. How does the graph change if one identifies the two edges R + M and tries to find the new graph to draw planar?

solution

  1. With complete induction on the number of vertices V.