
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
October 29th, 2011, 06:01 PM  #1 
Senior Member Joined: Apr 2011 From: Recife, BR Posts: 352 Thanks: 0  Graph theory and number theory
(Selfproposed) Given a graph with n vertices, assign a positive integer greater than one to each vertex, such that the integers are consecutive. Draw an edge connecting two vertices iff the numbers assigned to them and relatively prime. Is it possible for such a graph be planar for all ? For n = 6 just choose the numbers 11, 12, 13, 14, 15, 16. I couldn't find a possibility for n = 7 (haven't tried much though). Any ideas? 
October 30th, 2011, 01:09 AM  #2 
Senior Member Joined: Sep 2008 Posts: 150 Thanks: 5  Re: Graph theory and number theory
It is certainly not possible for any n. A very bad bound would be: It is not possible, if n is bigger than . If n is that big, one can easily find a complete graph with 5 vertices, which is contained (and known to be not planar). Here is how it works: Take k to be the smallest number in your numbering of the vertices, that is divisible by 2,3, and 5. Then the numbers k+1, k+2, k+3, k+5 and k+7 occure as numbers of vertices. However, the difference of two of them is at most 6, so only the primes 2,3, and 5 could divide two of them, but that is absurd, as 2 divids only k+2, 3 divides only k+3 and 5 divides only k+5. It follows, that these numbers are pairwise coprime, showing the assertion. I'm sure one can improve this bound easily, and exspect the bound to be in the area of 10. May be the 33 graph is even easier to find. rgds Peter 
October 30th, 2011, 08:49 AM  #3 
Senior Member Joined: Apr 2011 From: Recife, BR Posts: 352 Thanks: 0  Re: Graph theory and number theory
Thanks for the bound, Peter. I see by Turán we can have at most edges. Is there a similar theorem for complete bipartite subgraphs such as ? Because for n = 8 we need less than 24 edges, and if we choose (48 > 55) we have 19 edges but I still think it's not planar!

October 30th, 2011, 04:20 PM  #4 
Senior Member Joined: Apr 2011 From: Recife, BR Posts: 352 Thanks: 0  Re: Graph theory and number theory
I will show that Let be the set of n consecutive numbers. If , then there is a number such that and , which follows because given seven consecutive numbers, one of them, k, must be congruent to 2, 8 or 11 mod 15, thus given 13 consecutive numbers Consider the vertices to which k, k+1, k+2, k+3, k+5 and k+6 are assigned. Separate them in two groups : k, k+2, k+6 and k+1, k+3, k+5. There is an edge connecting (k, k+1), (k+1,k+2), (k+2,k+3) and (k+5,k+6) because they are consecutive. If k is not divisible by 3, there is an edge (k, k+3) and (k+3,k+6). If k is not divisible by 5, there is an edge (k,k+5). If k is not congruent to 1 modulo 3, there is an edge (k+2, k+5). If k is not congruent to 4 modulo 5, there is an edge connecting (k+1,k+6). Then these two groups form a complete bipartite graph, hence the graph is not planar. Putting the restrictions above together, we need k to be congruent to 2 modulo 3 and k to be congruent to 1, 2 or 3 modulo 5, thus if there is a k congruent to 2, 8 or 11 mod 15, then the graph is not planar, which is the case for as proven above. I am still not sure about n = 8, 9, 10, 11, 12 though. 

Tags 
graph, number, theory 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Edge chromatic number question (Graph theory)  Ecllipsers  Applied Math  0  February 9th, 2014 03:46 PM 
Graph theory: Linking graph characteristics and minimal cut  avnerg  Applied Math  0  September 18th, 2013 06:03 AM 
Graph Theory  sulonski  Applied Math  1  August 2nd, 2012 10:03 AM 
graph theory  social networks and reverting the graph  johnyjj2  Applied Math  0  December 28th, 2010 02:49 PM 
Graph Theory  davy89  Applied Math  1  November 30th, 2008 01:05 PM 