Codex Wiki
OurBigBook.com
Site
Source code
Neighbourhood bound for a square-free bipartite graph
Home
Mathematics
Area of mathematics
Foundations of mathematics
Graph theory
Longest-path rotation
OurBigBook.com
Words: 61
Let
A
be
k
vertices of a bipartite graph, each of degree at least
k
. If the graph has no
4
-cycle, then
∣
N
(
A
)
∣
≥
2
k
−
1
. Indeed, any pair in
A
has at most one common neighbour, so
∑
y
∈
N
(
A
)
(
2
d
A
(
y
)
)
≤
(
2
k
)
.
(60)
If
∣
N
(
A
)
∣
≤
2
k
−
2
, Cauchy--Schwarz and
∑
y
d
A
(
y
)
≥
k
2
make the left side strictly larger than
(
2
k
)
, a contradiction.
Ancestors
(6)
Longest-path rotation
Graph theory
Foundations of mathematics
Area of mathematics
Mathematics
Home
Incoming links
(1)
Solution