Exam 3

Question 1

Pigeonhole principle

Answer 1

if k is Z+ and k+1 objects are placed into k boxes, then one box contains two or more objects

Question 2

Generalized Pigeonhole Principle

Answer 2

If N objects are put into k boxes, then there is at least one box w/ N/k objects (ceiling)

Question 3

Permutation

Answer 3

Ordered arrangement

Question 4

r-Combination

Answer 4

r-combination of elems in an unordered selection of r elements from a set size n

Question 5

Permutation formula

Answer 5

n! / (n-r)!

Question 6

Combination formula

Answer 6

n! / ((n-r)! r!)

Question 7

The Binomial Theorem

Answer 7

(x+y)^n = Sigma(n,j) x^(n-j) * y^j

Question 8

Permutations with Repetition

Answer 8

n^r

Question 9

Combinations w/ Repetition

Answer 9

C(n+r-1, r)

Question 10

Simple graph

Answer 10

graph’s edges connect two different vertices. no two edges connect the same two vertices

Question 11

Multigraphs

Answer 11

graph has multiple edges connecting same two vertices

Question 12

Pseudograph

Answer 12

can have loops, multiple edges connecting same vertices

Question 13

Degree of vertex

Answer 13

Number of edges incident with it

Question 14

Neighbors of a vertex

Answer 14

N(v) = set of all neighbors of v

Question 15

Handshaking theorem

Answer 15

summed degrees of all vertices equal 2 times number of edges

Question 16

Simple path

Answer 16

doesn’t contain same vertex more than once

Question 17

An ___ graph has an ____ number of vertices of ____ degree

Answer 17

undirected, even, odd

Question 18

To form a euler path, every vertex must have a ___ degree

Answer 18

even