Intereting Posts

Prove that if $n$ is composite, then $(n-1)! \equiv 0 \pmod n$
How to prove that the set $\{\sin(x),\sin(2x),…,\sin(mx)\}$ is linearly independent?
Is a sequentially continuous map $f:E'\to E'$ continuous?
Weak* operator topology and finite rank operators
Proof by induction: $n$th Fibonacci number is at most $ 2^n$
field of algebraic numbers
Union of a countable collection of open balls
When does Initial Value Problems have: no solutions, more than one solution, precisely one solution?
Weak Derivative Heaviside function
Show that $\mathbb{Q}(\sqrt{2 +\sqrt{2}})$ is a cyclic quartic field i.e. is a galois extension of degree 4 with cyclic galois group
Are there open problems in Linear Algebra?
How to evaluate the sum
How to solve this integral: $ \int_{-1}^{1} \frac{x^4}{a^x+1}dx $?
What does | mean?
Do all vectors have direction and magnitude?

This is a problem I found in a graph theory text, but I can’t figure it out.

Let $S$ be a set of $n$ points in a plane, the distance between any two of which is at least one. Show that there are at most $3n$ pairs of points of $S$ at distance exactly one.

Experimenting, I figured the way to get the most points of distance exactly 1 would be to lay out the points in a grid made out of equilateral triangles. While building up this grid, it seems that when adding a new vertex, I can connect it to 2 or 3 other points to have distance exactly 1, which implies that I can only add at most 3 new pairs of points 1 unit apart for every point I add, which suggests the result. Is there a nonhandwavey way to show this?

- Equal sized partitions without overlap
- Help me to simplify $\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r}{i}\binom{r-i}{r-2i}$
- How many cards do you need to win this Set variant
- Coupon collector problem for collecting set k times.
- Proof sought for a sum involving binomials that simplifies to 1/2
- How many knight's tours are there?

- Counting integer partitions of n into exactly k distinct parts size at most M
- Show that $\frac{1}{1+x}H(\frac{x}{1+x})=\sum^\infty_{k=0}x^k$
- Computing the $n^{\textrm{th}}$ permutation of bits.
- How would I find a minimum weight spanning tree for W?
- Number of permutations which are products of exactly two disjoint cycles.
- Arrangement of word MISSISSIPPI in which no three S occur together
- Number of triangles inside given n-gon?
- Have any one studied this binomial like coefficients before?
- Probability of having exactly 1 pair from drawing 5 cards
- How to prove combinatorial identity $\sum_{k=0}^s{s\choose k}{m\choose k}{k\choose m-s}={2s\choose s}{s\choose m-s}$?

It’s natural (especially since this is a graph theory text…) to turn the set $S$ into a graph by connecting two points (vertices) if they are exactly one unit apart. What can you say about this graph? Can you say something about the degrees of the vertices? What, in terms of this graph, are you trying to prove?

Each point can have at most $6$ neighbours at distance $1$, so it can be in at most $6$ pairs. Each pair contains $2$ points. So there can be at most $6n/2=3n$ such pairs.

- Given a width, height and angle of a rectangle, and an allowed final size, determine how large or small it must be to fit into the area
- Prove that the identity map $(C,d_1) \rightarrow (C,d_\infty)$ is not continuous
- A finite module over a Noetherian ring is torsionless if and only if it is a submodule of a finite free module
- Prove this proprety of $f(x)$
- Why this polynomial represents this figure?
- Proving that one of $a(1-b), b(1-c), c(1-a) \le \frac{1}{4}$
- Boundedness of solutions for the Laplacian
- Odd-dimensional complex skew-symmetric matrix has eigenvalue $0$
- Expand $(\vec{A}\times \nabla)\times \vec{B}$ using tensorial notation
- Defining median for discrete distribution
- How to show the intersection of a prime ideal and a subring is a prime ideal
- A construction of sigma-algebras – surely not new, right?
- Questions about $f: \mathbb{R} \rightarrow \mathbb{R}$ with bounded derivative
- Why Zariski topology?
- what is the tensor product $\mathbb{H\otimes_{R}H}$