# What's the graph relation? #2

What's the relation that joins the nodes? Open the image in a new tab if you'd like to see the diagram with better resolution.

Previous

Hint 1

It is equally important to think about why any given two nodes are connected as it is to consider why they are not connected.

The numbers are connected if the prime representation of them has the same number of primes (can be non-distinct)

Example:

$$24=2^3\times3^1$$ so there are $$3+1=4$$ prime factors and $$16=2^4$$ which has $$4$$ prime factors so they are connected.
$$11=11^1$$ so there are $$1$$ prime factor and $$12=2^2\times3^1$$ so there are $$2+1=3$$ prime factors so they are not connected.

I thought it should be nice to include my thinking process:

All the primes are connected to each other. What is the same among the primes?
Oh! They have the same number of factors($$2$$)!
No, it doesn't applies for some connections.
Each graph is a complete graph.
After a while, I found out the connection between the numbers.

• Thanks for sharing your thought process! It's cool to see that you overcame the less obvious part of this puzzle. Apr 29, 2020 at 5:06

Solving process:

The graph clearly has four connected components, one of which contains all the primes from 2 to 19. In attempting to see what was connected to what within these components, and indeed if anything was disconnected, I found that in fact each connected component was complete -- i.e. the original graph was a labelling of $$K_9 \cup K_8 \cup K_4 \cup K_2$$. Thus, since the graph was undirected and each connected component obeyed transitivity, the adjacency relation was some kind of equivalence relation. So since one such equivalence class was "all the primes," I checked the factorizations of the rest of the nodes, and each connected component had nodes with the same length of factorization (without exponents, i.e. $$2*2*2*3$$ instead of $$2^3*3$$). Therefore...

Solution:

The adjacency relation is "has the same number of prime factors, including multiplicity."