MATH 301 Test 3 Flashcards
A relation is called a function (f: A -> B) if
f(a) = b and f(a) = c implies b=c
(a,b) ∈ R and (a,c) ∈ R implies b=c
The domain of a function f: A -> B is
dom(f) = {a : ∃b∈B, f(a)=b}
The image of a function f: A -> B is
im(f) = {b: ∃a∈A, f(a)=b}
If f: A->B is a function, dom(f)=A and im(f)⊆B, we call B the
codomain
The inverse of a function f is
f^(-1) = {(b,a) : (b,a) ∈ f}
f^(-1) is a function provided
(a,b) ∈ f^(-1) and (a,c) ∈ f^(-1) implies b=c
or (b,a) ∈ f and (c,a) ∈ f implies b=c
A function f: A->B is called injective or one-to-one provided
f(x1) = f(x2) implies x1 = x2
If f: A->B is one-to-one, then f^(-1) (is/is not) a function.
is
If f: A->B is one-to-one, the size of A and B are related as
|B| >= |A|
A function f: A->B is called surjective or onto B if
im(f)=B
∀b∈B, ∃a∈A s.t. f(a)=b
If f: A->B is onto, the size of A and B are related as
|A| >= |B|
A function f: A->B is called a bijection if
it is both one-to-one (injective) and onto (surjective)
If f: A->B is bijective, the size of A and B are related as
|A| = |B|
Let A and B be fintie sets with |A| = a and |B| = b. How many functions are there from A to B?
b^a
Let A and B be fintie sets with |A| = a and |B| = b. How many one-to-one functions are there from A to B?
b falling a
Let A and B be fintie sets with |A| = a and |B| = b. How many onto functions are there from A to B?
the sum from k=0 to b of
(-1)^k (b choose k) (b-k)^a
Pigeonhole Principle
If f: A->B is one-to-one, then |A| <= |B|
Contrapositive: If |A| > |B|, then there is no one-to-one function f: A->B
A graph is
a pair G=(V,E) where V is a finite set and E is a set of two-element subsets of V
Let u,v∈V. We say u is adjacent to v if
{u,v}∈E
Notation: u~v
The degree of v is
the number of edges with which v is incident
A graph is called regular if
every vertex has the same degree
Handshakes theorem
The sum of the degrees of the vertices in V(G) is equal to 2|E|
We say f: V(G) -> V(H) is an isomorphism provided
f is a bijection and a~b iff f(a)~f(b)
A clique is a graph G is
a set S⊆V(G) in which all vertices are pairwise adjacent
The size of the largest clique in G is called its
clique number, w(G)
A graph is complete if
all vertices are pairwise adjacent
Kn is the complete graph of n vertices
The vertex set of a complete graph is
a clique
Let G and H be graphs. We call G a subgraph of H if
V(G)⊆V(H) and E(G)⊆E(H)
A spanning subgraph also has
V(G) = V(H)
A subgraph G⊆H is called induced if
E(G)={{x,y}∈E(H) : x,y ∈ V(G)}
Notation: H[A] with A⊆V(H) is the subgraph of H induced by A
If G is a graph and e∈E(G), then G-e is
a graph with E(G-e) = E(G) - {e}
If G is a graph and v∈V(G), then G-v is
a graph with V(G-v) = V(G) - {v}
The complement of G is G bar, with
V(Gbar) = V(G) and E(Gbar) = {{x,y}∈VxV; {x,y} ∉ E}
An independent set is a set of
pairwise non-adjacent vertices
The size of a largest independent set in G is
the independence number, α(G)
A walk is
a sequence of vertices W=(v0, v1, …, vk) with v0~v1~…~vk
A path is
a walk with no repeated vertices
For u,v∈V(G), if there is a (u,v) walk in G, then
there is a (u,v) path in G
We say G is connected if
for every pair u,v∈V(G), there is a (u,v) path
A component of G is
a subgraph induced by an equivalence class of the “is-connected-to” relation
A vertex in a graph is called a cut-vertex if
G-v has more components than G
An edge in a graph is called a cut-edge if
G-e has more components than G
If G is a connected graph and e∈E(G) is a cut-edge, then G-e has ? components
exactly 2
A cycle is
a walk of length at least 3 with the first and last vertex the same and no other repeated vertices
A tree is
an acyclic connected graph
If T is a tree and u,v∈V(T), then there (is/is not) a unique (u,v) path in T
is
If G is a graph and for every pair of vertices u,v∈V(G) there is a unique (u,v) path in G, then G is
a tree
A vertex of degree 1 is called
a leaf
An acyclic graph is called
a forest
If T is a tree with at least two vertices, then T
has a leaf
If T is a tree and v is a leaf of T, then T-v
is a tree
If T is a tree with n vertices, then T has ? edges
n-1
Let G be a graph and let k∈Z+. A k-coloring of G is a function
f: V(G) -> {1,2,…,k}
We call a coloring proper proved
∀xy∈E(G), f(x) =/= f(y)
If a graph has a proper k-coloring, we call it
k-colorable (it will also be k+1 colorable etc)
The chromatic number is
the smallest positive integer k for which G is k-colorable
Notation: X(G)
A bipartite graph is
a graph that is 2-colorable
The vertices of a bipartite graph can be
partitioned as V(G) = A U B (where A ∩ B = Ø) so that every edge in G has one end in A and the other in B
Kn,m is the complete bipartite graph with
vertices V = A U B, |A|=n, |B|=m, and E(Kn,m) = {{a,b} : a ∈ A, b ∈ B}
The chromatic number of a graph lies between
w(G) <= X(G) <= Δ(G)+1
(the clique number of G is less than or equal to the chromatic number of G which is less than or equal to one more than the maximum vertex degree of G)
How to prove X(G) = k
- prove the graph is k-colorable
2. prove G is not k-1 colorable
Proving a wheel graph is k-colorable
Prove the coloring of the cycle (independence number will be floor(n/2) - these are the color classes; the chromatic number of a cycle is 2 if n is even and 3 if n is odd)
So, if the cycle needs 2/3 colors, then the wheel needs 3/4
