how to understand this theorem of graph theory a crossing number of $C_4 $ x $ C_4$?

132 Views Asked by At

definition A drawing of a graph G is optimal if it has the minimal number of possible crossings; this number is denoted v(G)

Let u be a degree 4 vertex in a graph G. In an optimal drawing of G there is no edge that crosses exactly three of the cdges incident with u.

Now the proof goes this way,

To the contrary, suppose an edge e crosses exactly three of the edges incident with u. In the order they are crossed as we traverse the edge e. call them $e_1, e_2,$ and $e_3,$ and call the remaining u-incident edge $e_4$. We can then create a new drawing of G with fewer crossings by relabeling as follows. The crossing of e and $e_2$ is the new location of v. \

im stack up in this up to the end of the statement

starting here : Proof continues ...

Detour e from its crossing with $e_1$. adding the section of $e_1$ between this crossing and the old location of u, and then adding the section of $e_3$ from there to the original crossing of e with $e_3$; complete e by adding the section that came after its original crossing with $e_3$. Modify $e_4$ by adding the section of $e_2$ between the old and new locations of u. In a similar manner, modify the edges $e_1$ and $e_3$. adding former sections of e to extend them to the vertex u. Removing

all "tangential" crossings leaves a drawing of G with at least two fewer crossings

How to easily understand this step of the proof very confusing??

1

There are 1 best solutions below

4
On

First, it's difficult to understand because it's a clunky proof. It's a good first draft of a proof, but it appears the author never had anyone read it over. The clunkiness is complicated by the typo in the statement, "The crossing of e and $e_2$ is the new location of v.". "v" should presumably have been "u". The reference to $C_4$, which plays no part in the theorem or proof, and the annoying, inexplicable and irrelevant redesignation of cr(G) as v(G) just adds to the confusion.

We want to prove that no edge in an optimal drawing of the graph G crosses exactly 3 edges adjacent to any vertex of degree 4. Assume the contrary, so we have the situation in the following picture.

enter image description here

The author then laboriously moves the vertex u and all 5 edges to produce a drawing in which only one of the four edges adjacent to u is crossed by edge e. I just moved e to get the following drawing. (The author's method would produce essentially the same drawing, just with everything slid to the right.)

enter image description here

Anyway, the new drawing has 2 fewer crossings than the original, meaning the assumption that the original had the minimum number of crossings was wrong.

=============================================================

As requested, a step by step creation of new drawing of G according to the given proof. I apologize for my lack of artistic skill.

"To the contrary, suppose an edge e crosses exactly three of the edges incident with u. In the order they are crossed as we traverse the edge e. call them $e_1$,$e_2$, and $e_3$, and call the remaining u-incident edge $e_4$." enter image description here

"The crossing of e and $e_2$ is the new location of v (sic). " enter image description here

"Detour e from its crossing with $e_1$. adding the section of $e_1$ between this crossing and the old location of u, and then adding the section of $e_3$ from there to the original crossing of e with $e_3$." enter image description here "Modify $e_4$ by adding the section of $e_2$ between the old and new locations of u." enter image description here "In a similar manner, modify the edges $e_1$ and $e_3$. adding former sections of e to extend them to the vertex u. Removing

all "tangential" crossings leaves a drawing of G with at least two fewer crossings" enter image description here