D420 Discrete Math: Functions and Relations - Set 5 - Part 2

Correct Answer: A list of vertex degrees in non-increasing order

The degree sequence of a graph is a list of the degrees of its vertices arranged in non-increasing order.

Correct Answer: A one-to-one correspondence between the vertices and edges of two graphs that preserves adjacency

An isomorphism between two graphs is a mapping between their vertices and edges that preserves the adjacency relationships.

Correct Answer: The minimum number of colors needed to color the vertices so that no two adjacent vertices share the same color

The chromatic number of a graph is the smallest number of colors required to color the vertices such that no two adjacent vertices are the same color.

Correct Answer: A graph where the removal of one vertex disconnects the graph

A cut-vertex is a vertex whose removal would disconnect the graph, splitting it into separate components.

Correct Answer: A cycle that visits every vertex of the graph exactly once and returns to the starting vertex

A Hamiltonian cycle is a closed path that visits every vertex of a graph exactly once and returns to the starting vertex.

Correct Answer: If more objects than containers are available, at least one container must hold more than one object

The pigeonhole principle states that if more objects than containers are available, at least one container must hold more than one object.

Correct Answer: A path that visits every edge of a graph exactly once but does not necessarily return to the starting vertex

An Euler path is a path that visits every edge of a graph exactly once, but unlike an Euler circuit, it does not necessarily return to the starting vertex.

Correct Answer: A subset of a set where all elements are equivalent under a given equivalence relation

An equivalence class is a subset of a set where all elements are equivalent to each other under a given equivalence relation.

Correct Answer: A set is countable if it is finite or has the same cardinality as the natural numbers

A set is countable if it is either finite or if its elements can be put into one-to-one correspondence with the natural numbers.

Correct Answer: A subset of the Cartesian product of A and B

A binary relation from set A to set B is a subset of the Cartesian product AB, which consists of ordered pairs where the first element is from A and the second is from B.

Correct Answer: It must be both injective and surjective

A bijective function is both injective (one-to-one) and surjective (onto), meaning every element of the domain maps to a unique element of the codomain, and all elements of the codomain are covered.

Correct Answer: pq

De Morgan's law states that (pq) is equivalent to pq, which distributes the negation across the conjunction and changes it to a disjunction.

Correct Answer: Rearranging the parentheses in an expression does not change the result

The associative property of Boolean algebra states that the result of a Boolean expression remains the same regardless of how the parentheses are arranged, as long as the operation remains the same.

Correct Answer: p(pq)=p

The absorption law in Boolean algebra states that p(pq) is equal to p, meaning that the term p "absorbs" the disjunction with q.

Correct Answer: A graph with no loops or parallel edges

A simple graph is a graph that has no loops (edges that connect a vertex to itself) and no parallel edges (multiple edges connecting the same pair of vertices).

Correct Answer: Assuming the statement is true for all previous cases up to the current one and proving it for the next case

Strong mathematical induction involves assuming that the statement is true for all previous cases up to the current one, and then proving it for the next case.

Correct Answer: There is no other element in the set that is smaller

A minimal element in a partially ordered set is one for which there is no other element in the set that is smaller in the ordering.

Correct Answer: The dot product of each row of the first matrix with each column of the second matrix

The matrix product involves taking the dot product of each row in the first matrix with each column in the second matrix to form the resulting matrix.

Correct Answer: A matrix where all non-diagonal elements are zero

A diagonal matrix is a square matrix in which all the elements not on the main diagonal are zero.

Correct Answer: A diagonal matrix where all diagonal elements are 1

The identity matrix is a diagonal matrix in which all the diagonal elements are 1, and all other elements are 0.