Question

Let n ≥ 2. Define Gn to be the graph whose vertices are the integers 2, 3, . . . , n. Two vertices are adjacent if and only if the two corresponding numbers are relatively prime, that is, their gcd is 1. Find a particular k such that Gk is not planar. (It is not necessary to find the smallest k with this property.)

Answer 1

Solution:-

Given

For k = 11, is not a planar graph. Because in this graph, two vertices 11 and 7 have an edge with each of other vertices.

( gcd(11, n) = gcd (7, n) = 1 for all n = 2, 3, 4, 5, 6, 8, 10 and gcd (11, 7) = 1)

We draw the graph , we draw the edges b/w vertices m and n such that gcd (m, n) = 1

Now we can see that

gcd (2, 5) = 1

gcd (3, 8) = 1

gcd (3, 5) = 1

gcd (2, 9) = 1

gcd (3, 10) = 1

gcd (5, 8) = 1

But we can not draw the edges between these vertices without crossing any edge.

If we draw these edges, then must be non-planar graph.

Thus, is not planar.

Thanks for supporting...

Please give positive rating...