Skip to main content
MathOverflow

Return to Answer

added 4 characters in body
Source Link
Dominic van der Zypen
Dominic van der Zypen
  • 48.9k
  • 8
  • 47
  • 162

The answer to the question is Yes.

Consider the complete graph on $n$ vertices with one edge removed. It is easy to see that the 2 vertices adjacent to the sole edge that was removed are the only ones that are not popular. So the share of popular vertices is $\frac{m-2}{m}$$\frac{n-2}{n}$, which converges to 1$1$ as m$n$ grows large.

The answer to the question is Yes.

Consider the complete graph on $n$ vertices with one edge removed. It is easy to see that the 2 vertices adjacent to the sole edge that was removed are the only ones that are not popular. So the share of popular vertices is $\frac{m-2}{m}$, which converges to 1 as m grows large.

The answer to the question is Yes.

Consider the complete graph on $n$ vertices with one edge removed. It is easy to see that the 2 vertices adjacent to the sole edge that was removed are the only ones that are not popular. So the share of popular vertices is $\frac{n-2}{n}$, which converges to $1$ as $n$ grows large.

Source Link
Dominic van der Zypen
Dominic van der Zypen
  • 48.9k
  • 8
  • 47
  • 162

The answer to the question is Yes.

Consider the complete graph on $n$ vertices with one edge removed. It is easy to see that the 2 vertices adjacent to the sole edge that was removed are the only ones that are not popular. So the share of popular vertices is $\frac{m-2}{m}$, which converges to 1 as m grows large.