Theoretical Computer Science Cheat Sheet
Number Theory Graph Theory
The Chinese remainder theorem: There ex-
ists a number C such that:
C ≡ r
1
mod m
1
.
.
.
.
.
.
.
.
.
C ≡ r
n
mod m
n
if m
i
and m
j
are relatively prime for i = j.
Euler’s function: φ(x) is the number of
positive integers less than x relatively
prime to x.If
n
i=1
p
e
i
i
is the prime fac-
torization of x then
φ(x)=
n
i=1
p
e
i
−1
i
(p
i
− 1).
Euler’s theorem: If a and b are relatively
prime then
1 ≡ a
φ(b)
mod b.
Fermat’s theorem:
1 ≡ a
p−1
mod p.
The Euclidean algorithm: if a>bare in-
tegers then
gcd(a, b) = gcd(a mod b, b).
If
n
i=1
p
e
i
i
is the prime factorization of x
then
S(x)=
d|x
d =
n
i=1
p
e
i
+1
i
− 1
p
i
− 1
.
Perfect Numbers: x is an even perfect num-
ber iff x =2
n−1
(2
n
−1) and 2
n
−1 is prime.
Wilson’s theorem: n is a prime iff
(n − 1)! ≡−1modn.
M¨obius inversion:
µ(i)=
1ifi =1.
0ifi is not square-free.
(−1)
r
if i is the product of
r distinct primes.
If
G(a)=
d|a
F (d),
then
F (a)=
d|a
µ(d)G
a
d
.
Prime numbers:
p
n
= n ln n + nln ln n − n + n
ln ln n
ln n
+ O
n
ln n
,
π(n)=
n
ln n
+
n
(ln n)
2
+
2!n
(ln n)
3
+ O
n
(ln n)
4
.
Definitions:
Loop An edge connecting a ver-
tex to itself.
Directed Each edge has a direction.
Simple Graph with no loops or
multi-edges.
Walk A sequence v
0
e
1
v
1
...e
v
.
Trail A walk with distinct edges.
Path A trail with distinct
vertices.
Connected A graph where there exists
a path between any two
vertices.
Component A maximal connected
subgraph.
T ree A connected acyclic graph.
F ree tree A tree with no root.
DAG Directed acyclic graph.
Eulerian Graph with a trail visiting
each edge exactly once.
Hamiltonian Graph with a cycle visiting
each vertex exactly once.
Cut A set of edges whose re-
moval increases the num-
ber of components.
Cut-set A minimal cut.
Cut edge A size 1 cut.
k-Connected A graph connected with
the removal of any k − 1
vertices.
k-Tough ∀S ⊆ V,S = ∅ we have
k ·c(G − S) ≤|S|.
k-Regular A graph where all vertices
have degree k.
k-Factor A k-regular spanning
subgraph.
Matching A set of edges, no two of
which are adjacent.
Clique A set of vertices, all of
which are adjacent.
Ind. set A set of vertices, none of
which are adjacent.
Vertex cover A set of vertices which
cover all edges.
Planar graph A graph which can be em-
beded in the plane.
Plane graph An embedding of a planar
graph.
v∈V
deg(v)=2m.
If G is planar then n − m + f =2,so
f ≤ 2n − 4,m≤ 3n − 6.
Any planar graph has a vertex with de-
gree ≤ 5.
Notation:
E(G) Edge set
V (G) Vertex set
c(G) Number of components
G[S] Induced subgraph
deg(v) Degree of v
∆(G) Maximum degree
δ(G) Minimum degree
χ(G) Chromatic number
χ
E
(G) Edge chromatic number
G
c
Complement graph
K
n
Complete graph
K
n
1
,n
2
Complete bipartite graph
r
(k, ) Ramsey number
Geometry
Projective coordinates: triples
(x, y, z), not all x, y and z zero.
(x, y, z)=(cx, cy, cz) ∀c =0.
Cartesian Projective
(x, y)(x, y, 1)
y = mx + b (m, −1,b)
x = c (1, 0, −c)
Distance formula, L
p
and L
∞
metric:
(x
1
− x
0
)
2
+(y
1
− y
0
)
2
,
|x
1
− x
0
|
p
+ |y
1
− y
0
|
p
1/p
,
lim
p→∞
|x
1
− x
0
|
p
+ |y
1
− y
0
|
p
1/p
.
Area of triangle (x
0
,y
0
), (x
1
,y
1
)
and (x
2
,y
2
):
1
2
abs
x
1
− x
0
y
1
− y
0
x
2
− x
0
y
2
− y
0
.
Angle formed by three points:
θ
(0, 0)
(x
1
,y
1
)
(x
2
,y
2
)
2
1
cos θ =
(x
1
,y
1
) · (x
2
,y
2
)
1
2
.
Line through two points (x
0
,y
0
)
and (x
1
,y
1
):
xy1
x
0
y
0
1
x
1
y
1
1
=0.
Area of circle, volume of sphere:
A = πr
2
,V=
4
3
πr
3
.
If I have seen farther than others,
it is because I have stood on the
shoulders of giants.
– Issac Newton