# Meaning of Nc in Paul Erdős and Rényi's paper On Random Graphs

In Paul Erdős and Rényi's 1959 paper On Random Graphs I, they describe the number of edges in a random graph by the function

(1) Nc = [1/2 * nlogn + cn]

where n is the number of nodes in the graph, c is "an arbitrary fixed real number" and [x] denotes the integer part of x. They go on to use a number of graphs of the form G(n, Nc), where G(n, Nc) denotes a random graph with n nodes and Nc edges.

Nc appears to be an arbitrary (?) function to return a number of edges based on some c and n, but I don't understand how c is selected or why the function is relevant. When the authors discuss graphs of the type G(n, Nc), is there any special property besides the graph just having some arbitrary number of edges? I.e, could I replace Nc with some function for a random number of edges between 0 and the maximum possible edges for the graph with the same results?

-
Note that characters with and without diacritical marks rarely represent similar phonemes. "Erdos" is about as badly misspelled as "Erdis", though it may look more similar. If you can't produce a character with a diacritical mark on your keyboard, you can copy it from the Web. – joriki May 10 '12 at 17:56
In that case, Rényi has a diacritical mark too. – anonymous May 10 '12 at 18:05
Added, thank you for pointing that out. – pleiotrope May 10 '12 at 18:53

$N_c$ is a more-or-less arbitrary function, but its choice defines the class of random graphs being studied. So you could replace it with a different function, but it would change the correct statements of all their theorems. Note that the statements of the theorems depend on $c$, so you don't have to worry about choosing a specific $c$.
I see, thank you. However, in the proof of the Lemma, they state that for some graph G(n, $N_c$) with r connected components and $l_i$ points on each component (i = 1,2,...,r), that the sum of all the possible edge choices for each component is ≥ $N_c$. (This is better described in the paper on p 293). However, for a graph G(5, 10) (with $c$=1.15) having two connected components of 2 and 3 points each, that sum is 4 while $N_c$ is 10. Should I take that relation as a condition bounding c, or does it fall from a property of the graph that I'm missing? – pleiotrope May 10 '12 at 18:50
A graph $G(5,10)$ can't have two connected components of 2 and 3 points each -- to be a $G(5,10)$ means you have 10 edges, and (as you've noted) such a graph would have at most 4 edges. – Micah May 10 '12 at 19:06