Hacker News Reader

I know a bit of graph theory, followed some courses at the university and worked on some graph problems [1], but the third definition in the book for 'n-th coprimality graph' was something I had never heard about. Then I also noticed that the author takes the natural numbers as the edges of his graph definition, which I think is not a common approach [2]

[1] https://www.iwriteiam.nl/counting.html

[2] https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)#G...

View on HN

The author is using the usual definition where vertices are an arbitrary (finite) set and edges are pairs of vertices. From the book:

Definition 2.1.1. A simple graph is a pair (V, E), where V is a finite set, and where E is a subset of P_2(V).

Sure in some examples V happens to be a set of natural numbers and then edges must be pairs if natural numbers, but there's nothing weird with that as any set would do. (Incidentally in model theory countably infinite graphs are often assumed to have as underlying set the naturals because it is convenient notationwise)

I agree, I am wrong, I comment too soon, not noticing that these were examples, not definitions.

Nah, those edges are not natural numbers, at least not until multigraphs (whose edges can be anything, including natural numbers, though they rarely are). You might have missed the convention to write the edge {i,j} as ij.

Reply on news.ycombinator.com