Graph Theory Concepts Quiz

Play an AI-generated podcast conversation about this lesson

What is true about a connected graph with n vertices?

It contains exactly 1 cycle if there are n edges. (correct)

It has at least n edges and can contain multiple cycles.

It must be disconnected if n is greater than 1.

It must be acyclic and thus cannot have any edges.

If a binary tree has a height of h, how many leaves can it have at most?

h + 1

2h

2^h (correct)

h^2

In a tree with n > 1 vertices, how many leaves will it have at least?

n - 2

1

2 (correct)

n

How many leaves does any tree with maximum degree ∆ have at least?

≥ ∆ leaves Signup and view all the answers

What is a spanning tree?

A spanning subgraph that is also acyclic. Signup and view all the answers

If a graph is k-colorable, what does this imply?

It can be colored using k colors without adjacent vertices sharing the same color. Signup and view all the answers

What defines a bipartite graph?

It can be colored using 2 colors. Signup and view all the answers

What characterizes a vertex in a tree as a leaf?

It has a degree of 1. Signup and view all the answers

What condition indicates that a connected graph G is Eulerian?

All vertices in G have even degree. Signup and view all the answers

In a bipartite graph G = (X, Y, E), what is necessary for G to have a perfect matching?

For all subsets A ⊆ (X ∪ Y ), the inequality |A| ≤ |N (A)| must hold. Signup and view all the answers

What can be deduced about a graph G with n ≥ 3 vertices if every vertex has degree at least n/2?

G contains a Hamiltonian path. Signup and view all the answers

What is the independence number of a graph G, denoted by α(G)?

The size of the largest independent set in G. Signup and view all the answers

What characterizes a tournament graph?

It has at least one Hamiltonian path. Signup and view all the answers

What remains true about an Eulerian graph if one edge is removed?

It will remain connected. Signup and view all the answers

In a k-regular bipartite graph, what is guaranteed?

It has a perfect matching. Signup and view all the answers

If a graph G has an Eulerian circuit, what can be concluded about its edges?

They can be partitioned into edge-disjoint cycles. Signup and view all the answers

What characterizes a set A as a subset of set B?

Every element of A is also an element of B. Signup and view all the answers

Which of the following statements is true about event outcomes in a sample space?

An event occurs if there exists an outcome in the sample space related to it. Signup and view all the answers

What is the definition of an edge in a graph?

An edge connects two nodes in a set of edges. Signup and view all the answers

If sets S, T, and R are given, which of the following expresses a correct relationship?

S , (T , R) is a subset of (S , T) ∪ R. Signup and view all the answers

What does the degree of a vertex in a graph represent?

The total number of edges connected to that vertex. Signup and view all the answers

In the context of induction as a proof technique, what are the essential components?

Base case, induction hypothesis, induction step. Signup and view all the answers

Which of the following statements about set operations is incorrect?

S \ (T \ R) is disjoint from R. Signup and view all the answers

What does it mean for sets A and B if A ⊆ B and A ≠ B?

A must be a proper subset of B. Signup and view all the answers

What does it mean for p to be a necessary condition for q?

If p is false, then q must also be false Signup and view all the answers

How is an even integer defined in terms of its prime factorization?

An even integer is defined as n = 2k for some integer k Signup and view all the answers

What does the prime factorization theorem state?

Every positive integer can be uniquely represented as a product of primes Signup and view all the answers

Which of the following correctly describes a prime integer?

An integer greater than 0 that has exactly two distinct positive divisors Signup and view all the answers

If the sum of two integers is even, what can be concluded about their difference?

Their difference is always even Signup and view all the answers

For any integer n, which statement is true if n is odd?

n + n + 1 is always odd Signup and view all the answers

What is the inequality related to the factorial of n?

n! < n^n for all n > 1 Signup and view all the answers

In the expression $X a(r^{n+1} - 1) = \frac{a_i}{r-1}$, what does it signify when $r \neq 1$?

It indicates the sum of a geometric series Signup and view all the answers

What does the variance measure in statistics?

How much a random variable deviates from its mean Signup and view all the answers

Which formula correctly represents the variance of a random variable X?

V[X] = E[X^2] - E[X]^2 Signup and view all the answers

What does the standard deviation represent about a random variable?

The variability around the mean Signup and view all the answers

In a directed graph, what do the vertices represent?

The elements of a set Signup and view all the answers

How is the inverse of a relation R from set A to set B represented?

R−1 = {(b, a)|(a, b) ∈ R} Signup and view all the answers

When two functions are considered equal, which of the following must be true?

They have the same domain, codomain, and mapping Signup and view all the answers

In the context of directed graphs, what does an edge from vertex u to vertex u represent?

A self-loop or reflexive relation Signup and view all the answers

Which statement about independent random variables X and Y is true?

Their joint distribution can be expressed as the product of their individual distributions Signup and view all the answers

What is the correct definition of a function from set A to set B?

A relation from A to B where each element in A maps to exactly one distinct element in B. Signup and view all the answers

Which of these statements about functions is true?

If f and g are injective, then g ◦ f is injective. Signup and view all the answers

Which of the following correctly describes equivalence relations?

The intersection of two equivalence relations is guaranteed to be an equivalence relation. Signup and view all the answers

What does the range of a function f, denoted as Ran(f), represent?

The set of all images b in B such that there exists an a in A with (a, b) in f. Signup and view all the answers

What characterizes a surjective function?

Every element in the codomain B is an image of at least one element from domain A. Signup and view all the answers

What does it mean for a relation R on set A to be transitive?

For any elements a, b, c in A, if (a,b) and (b,c) are in R, then (a,c) must also be in R. Signup and view all the answers

Which statement is true regarding the elements of an equivalence class?

All elements in an equivalence class are related to each other by the relation R. Signup and view all the answers

Which property is NOT necessarily true for the intersection of two equivalence relations on set A?

The intersection must contain all equivalence classes from both relations. Signup and view all the answers