On Feb 26, 7:17 pm, <fc3a...@uni-hamburg.de> wrote: > Warning, incoming lousy ASCII, change to fixed font :-) > > o o o > | | | > | O | > \ /|\ / > X | X > / \|/ \ > | O | > | | | > o o o > > The lines |/\ are tied to the unmovable nodes Oo. > (As you see, four lines come out of O and one out of o.) > X denotes a crossing, which is like a virtual crossing > from knot theory, i.e. you can move it ad lib and any > line over any other. Should they cross in the process, > well duh, then you have more crossings.) > > Can you move the lines around such that no horizontal > line going through this graph cuts more than three > of these lines? I think no, but can you lend me a > formal proof? > -- > Hauke Reddmann <:-EX8 fc3a...@uni-hamburg.de > Die Weltformel: IQ+dB=const.
Proofs in knot theory aren't my thing , but here's a shot : Label the knots with numbers :
denoting four 'levels of height' . 1 path directly connects 4 to 3 2 paths directly connect 4 to 2
If you choose a horizontal coordinate for your line situated between k and (k+1) levels of height, your line will cross at least all the paths taken from m to n , for all m <= k and all n>=(k+1) .
So the minimum number of paths cut between 4 and 3 is 2+1 = 3 Analogous reasoning shows the minimum number of paths between 2 and 3 is : 2 paths from 4 - 2 + 2 paths from 1 - 3 + 1 path from 2- 3 = five paths .
As shown in a previous post , it is indeed possible to rearrange the lines so that paths 'appear to coincide' , o o o \|/ O | O /|\ o o o
but whether this is considered 'cheating' or not is another manner .