MATH 301 Test 3

Question 1

A relation is called a function (f: A -> B) if

Answer 1

f(a) = b and f(a) = c implies b=c

(a,b) ∈ R and (a,c) ∈ R implies b=c

Question 2

The domain of a function f: A -> B is

Answer 2

dom(f) = {a : ∃b∈B, f(a)=b}

Question 3

The image of a function f: A -> B is

Answer 3

im(f) = {b: ∃a∈A, f(a)=b}

Question 4

If f: A->B is a function, dom(f)=A and im(f)⊆B, we call B the

Answer 4

codomain

Question 5

The inverse of a function f is

Answer 5

f^(-1) = {(b,a) : (b,a) ∈ f}

Question 6

f^(-1) is a function provided

Answer 6

(a,b) ∈ f^(-1) and (a,c) ∈ f^(-1) implies b=c

or (b,a) ∈ f and (c,a) ∈ f implies b=c

Question 7

A function f: A->B is called injective or one-to-one provided

Answer 7

f(x1) = f(x2) implies x1 = x2

Question 8

If f: A->B is one-to-one, then f^(-1) (is/is not) a function.

Answer 8

is

Question 9

If f: A->B is one-to-one, the size of A and B are related as

Answer 9

|B| >= |A|

Question 10

A function f: A->B is called surjective or onto B if

Answer 10

im(f)=B

∀b∈B, ∃a∈A s.t. f(a)=b

Question 11

If f: A->B is onto, the size of A and B are related as

Answer 11

|A| >= |B|

Question 12

A function f: A->B is called a bijection if

Answer 12

it is both one-to-one (injective) and onto (surjective)

Question 13

If f: A->B is bijective, the size of A and B are related as

Answer 13

|A| = |B|

Question 14

Let A and B be fintie sets with |A| = a and |B| = b. How many functions are there from A to B?

Answer 14

b^a

Question 15

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?

Answer 15

b falling a

Question 16

Let A and B be fintie sets with |A| = a and |B| = b. How many onto functions are there from A to B?

Answer 16

the sum from k=0 to b of

(-1)^k (b choose k) (b-k)^a

Question 17

Pigeonhole Principle

Answer 17

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

Question 18

A graph is

Answer 18

a pair G=(V,E) where V is a finite set and E is a set of two-element subsets of V

Question 19

Let u,v∈V. We say u is adjacent to v if

Answer 19

{u,v}∈E

Notation: u~v

Question 20

The degree of v is

Answer 20

the number of edges with which v is incident

Question 21

A graph is called regular if

Answer 21

every vertex has the same degree

Question 22

Handshakes theorem

Answer 22

The sum of the degrees of the vertices in V(G) is equal to 2|E|

Question 23

We say f: V(G) -> V(H) is an isomorphism provided

Answer 23

f is a bijection and a~b iff f(a)~f(b)

Question 24

A clique is a graph G is

Answer 24

a set S⊆V(G) in which all vertices are pairwise adjacent

Question 25

The size of the largest clique in G is called its

Answer 25

clique number, w(G)

Question 26

A graph is complete if

Answer 26

all vertices are pairwise adjacent

Kn is the complete graph of n vertices

Question 27

The vertex set of a complete graph is

Answer 27

a clique

Question 28

Let G and H be graphs. We call G a subgraph of H if

Answer 28

V(G)⊆V(H) and E(G)⊆E(H)

Question 29

A spanning subgraph also has

Answer 29

V(G) = V(H)

Question 30

A subgraph G⊆H is called induced if

Answer 30

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

Question 31

If G is a graph and e∈E(G), then G-e is

Answer 31

a graph with E(G-e) = E(G) - {e}

Question 32

If G is a graph and v∈V(G), then G-v is

Answer 32

a graph with V(G-v) = V(G) - {v}

Question 33

The complement of G is G bar, with

Answer 33

V(Gbar) = V(G) and E(Gbar) = {{x,y}∈VxV; {x,y} ∉ E}

Question 34

An independent set is a set of

Answer 34

pairwise non-adjacent vertices

Question 35

The size of a largest independent set in G is

Answer 35

the independence number, α(G)

Question 36

A walk is

Answer 36

a sequence of vertices W=(v0, v1, …, vk) with v0~v1~…~vk

Question 37

A path is

Answer 37

a walk with no repeated vertices

Question 38

For u,v∈V(G), if there is a (u,v) walk in G, then

Answer 38

there is a (u,v) path in G

Question 39

We say G is connected if

Answer 39

for every pair u,v∈V(G), there is a (u,v) path

Question 40

A component of G is

Answer 40

a subgraph induced by an equivalence class of the “is-connected-to” relation

Question 41

A vertex in a graph is called a cut-vertex if

Answer 41

G-v has more components than G

Question 42

An edge in a graph is called a cut-edge if

Answer 42

G-e has more components than G

Question 43

If G is a connected graph and e∈E(G) is a cut-edge, then G-e has ? components

Answer 43

exactly 2

Question 44

A cycle is

Answer 44

a walk of length at least 3 with the first and last vertex the same and no other repeated vertices

Question 45

A tree is

Answer 45

an acyclic connected graph

Question 46

If T is a tree and u,v∈V(T), then there (is/is not) a unique (u,v) path in T

Answer 46

is

Question 47

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

Answer 47

a tree

Question 48

A vertex of degree 1 is called

Answer 48

a leaf

Question 49

An acyclic graph is called

Answer 49

a forest

Question 50

If T is a tree with at least two vertices, then T

Answer 50

has a leaf

Question 51

If T is a tree and v is a leaf of T, then T-v

Answer 51

is a tree

Question 52

If T is a tree with n vertices, then T has ? edges

Answer 52

n-1

Question 53

Let G be a graph and let k∈Z+. A k-coloring of G is a function

Answer 53

f: V(G) -> {1,2,…,k}

Question 54

We call a coloring proper proved

Answer 54

∀xy∈E(G), f(x) =/= f(y)

Question 55

If a graph has a proper k-coloring, we call it

Answer 55

k-colorable (it will also be k+1 colorable etc)

Question 56

The chromatic number is

Answer 56

the smallest positive integer k for which G is k-colorable

Notation: X(G)

Question 57

A bipartite graph is

Answer 57

a graph that is 2-colorable

Question 58

The vertices of a bipartite graph can be

Answer 58

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

Question 59

Kn,m is the complete bipartite graph with

Answer 59

vertices V = A U B, |A|=n, |B|=m, and E(Kn,m) = {{a,b} : a ∈ A, b ∈ B}

Question 60

The chromatic number of a graph lies between

Answer 60

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)

Question 61

How to prove X(G) = k

Answer 61

1. prove the graph is k-colorable

2. prove G is not k-1 colorable

Question 62

Proving a wheel graph is k-colorable

Answer 62

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