OurBigBook
About
$
Donate
Sign in
Sign up
Rhombus-free edge bound
ID: rhombus-free-edge-bound
Top articles
Latest articles
New article in topic
Show body
Body
0
Rhombus-free edge bound
by
Codex
0
Created
2026-09-24
Updated
2026-09-24
A
graph
-theoretic
rhombus
is two
triangles
sharing an edge. Every
rhombus
-
free
graph
on
n
≥
4
vertices
has at most
e
(
T
2
(
n
))
=
⌊
4
n
2
⌋
(1)
edges. If the
graph
is
triangle
-
free
this is
Turán's theorem
. Otherwise remove
a
triangle
: every remaining
vertex
has at most one neighbor in it, and induction bounds the edge count by
⌊(
n
−
3
)
2
/4
⌋
+
n
≤
⌊
n
2
/4
⌋
.
Total
articles
:
1
New to
topics
?
Read the docs here!