Discrete Math Quiz: Degrees Paths And Connectivity

11 questions · exam conditions

0:00

Degrees Paths And ConnectivityQuestion 1 of 11

A tournament (directed complete graph) on 5 vertices has the property that every vertex can reach every other vertex by a directed path of length at most 2. What is the minimum possible number of vertices with out-degree 3 or higher?

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Degrees Paths And Connectivity

Practice Degrees Paths And Connectivity in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Degrees Paths And Connectivity, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

1
2 (correct answer)
3
0

Explanation: In a tournament on 5 vertices, each vertex has out-degree between 0 and 4. For every vertex to reach every other in at most 2 steps, vertices with low out-degree must be reachable from high out-degree vertices. If fewer than 2 vertices had out-degree ≥ 3, there wouldn't be enough 'hub' vertices to ensure the 2-step reachability condition. The minimum configuration requires exactly 2 vertices with out-degree ≥ 3. Choice A (1) provides insufficient connectivity. Choice C (3) is more than necessary. Choice D (0) cannot satisfy the reachability constraint.

Question 2

Graph $G$ is connected and has 12 edges. When vertex $u$ is removed along with all its incident edges, the resulting graph has exactly 3 connected components. If one of these components is a single isolated vertex, what is the minimum possible degree of vertex $u$ in the original graph?

3 (correct answer)
4
5
2

Explanation: Let

u

have degree

d

. After removing

u

, we get 3 components, one being an isolated vertex

v

. Originally,

v

was connected only to

u

, so

u

has at least one edge to

v

. The remaining two components must have been connected through

u

, requiring at least 2 more edges from

u

(one to each component). Thus

d ≥ 3

. This minimum is achievable. Choice D (2) cannot create 3 components with the given constraints. Choices B and C are larger than necessary.

Question 3

In graph $H$ , every vertex has degree exactly 3, and $H$ has girth 4 (shortest cycle length is 4). If $H$ has 8 vertices, what is the maximum number of vertices that can be at distance exactly 2 from a given vertex $v$ ?

3
4
6 (correct answer)
1

Explanation: Vertex

v

has 3 neighbors at distance 1. Since the girth is 4, no triangles exist, so

v

's neighbors aren't connected to each other. Each neighbor has degree 3, so each connects to

v

and 2 other vertices. These other vertices must be at distance ≥ 2 from

v

. With 8 total vertices: 1 (

v

) + 3 (distance 1) + at most 6 others can be at distance 2, which is achievable. Choice A and D are too restrictive. Choice B doesn't account for all possible distance-2 vertices from each neighbor.

Question 4

In a simple graph, vertex $v$ has degree 4 and is connected to vertices $a$ , $b$ , $c$ , and $d$ . If removing vertex $v$ and all its incident edges disconnects the graph into exactly 3 connected components, what can be concluded about the original graph structure?

At least two of the neighbors of $v$ were in different components before $v$ was added
Exactly one of $a$ , $b$ , $c$ , $d$ was connected to all the others before $v$ was removed
The neighbors $a$ , $b$ , $c$ , $d$ form exactly one edge among themselves in the original graph
At most one pair among $a$ , $b$ , $c$ , $d$ can be connected by a path not involving $v$ (correct answer)

Explanation: If removing

v

creates 3 components, then among

v

's four neighbors

\{a,b,c,d\}

, at most one pair can be in the same component (connected by a path not through

v

). Otherwise, we'd have fewer than 3 components. Choice A is incorrect because the neighbors could have been connected before adding

v

. Choice B incorrectly assumes one neighbor connects to all others. Choice C is too specific about the exact number of edges among neighbors.

Question 5

Consider a graph where every vertex has even degree, and the graph has exactly 2 connected components. If one component has 5 vertices and 6 edges, and the other component has 4 vertices, what is the minimum number of edges in the second component?

4
2 (correct answer)
6
0

Explanation: For the second component with 4 vertices where every vertex has even degree, we need the minimum number of edges to maintain connectivity. Since each vertex must have even degree ≥ 0, the smallest positive even degree is 2. For connectivity with 4 vertices, we need at least 3 edges, but this would create degree sum 6, which cannot be distributed as all even degrees with connectivity. The minimum is achieved with 2 vertices of degree 2 and 2 vertices of degree 0, but this creates disconnection. For a connected component, the minimum even degree configuration is all vertices having degree 2, giving 4 vertices × 2 = 8 total degree, so 4 edges. However, we can achieve connectivity with just 2 edges if two vertices have degree 2 and two have degree 0, forming a single edge component plus isolated vertices. Since the problem asks for a connected component, the minimum is 2 edges forming a path of length 1 with degrees (2,2,0,0), but this violates connectivity. The actual minimum for a connected component with all even degrees is 2 edges in a cycle of length 3 is impossible with 4 vertices. The minimum is 2 edges forming one connected piece.

Question 6

A graph $G$ with 8 vertices has vertex connectivity $\kappa(G) = 2$ and edge connectivity $\lambda(G) = 3$ . If the minimum degree $\delta(G) = 4$ , which statement must be true?

$G$ has exactly 2 cut vertices that when removed disconnect the graph
$G$ contains a vertex cut of size 2 but no smaller vertex cut exists (correct answer)
Removing any 3 edges from $G$ will always disconnect the graph
Every vertex in $G$ has degree at least 4 and at most 6

Explanation: Vertex connectivity

\kappa(G) = 2

means the minimum number of vertices whose removal disconnects

G

is 2, so there exists a vertex cut of size 2 and no smaller vertex cut exists (since

\kappa > 1

, the graph is connected and has no cut vertices). Option A misunderstands vertex connectivity - it's about vertex cuts, not cut vertices. Option C is wrong because edge connectivity

\lambda(G) = 3

means you need to remove at least 3 edges to disconnect, so removing any 3 edges might not disconnect it. Option D incorrectly assumes an upper bound on degree that isn't given.

Question 7

A graph $G$ has 8 vertices and every vertex has degree at least 3. What is the minimum number of edges that $G$ must have?

12 (correct answer)
24
16
10

Explanation: By the handshaking lemma, the sum of all vertex degrees equals twice the number of edges. Since each of the 8 vertices has degree at least 3, the sum of degrees is at least 8 × 3 = 24. Therefore, 2|E| ≥ 24, so |E| ≥ 12. The minimum is 12 edges. Choice B (24) incorrectly uses the sum of degrees as the number of edges. Choice C (16) might result from miscounting or using an incorrect formula. Choice D (10) is too small to satisfy the degree constraints.

Question 8

In graph $H$ , removing any single edge increases the number of connected components by exactly 1. Additionally, $H$ has 9 vertices and 8 edges. What is the number of vertices of degree 1 in $H$ ?

6 (correct answer)
4
2
8

Explanation: Since removing any edge increases components by 1,

H

is a forest (no cycles) where every edge is a bridge. With 9 vertices and 8 edges,

H

is connected and therefore a tree. Let

n_1, n_2, n_3, ...

be the number of vertices of degrees 1, 2, 3, etc. We have

n_1 + n_2 + n_3 + ... = 9

and

1 \cdot n_1 + 2 \cdot n_2 + 3 \cdot n_3 + ... = 16

(twice the number of edges). For any tree,

n_1 \geq 2

. Since the tree is connected with these constraints, the minimum degree is 1 and maximum practical degree with 8 edges is small. Working through the degree equation: if most vertices have degree 1 or 2, then

n_1 = 6, n_2 = 2, n_3 = 1

gives

6(1) + 2(2) + 1(3) = 13

... Actually,

n_1 = 6, n_2 = 1, n_4 = 2

gives

6(1) + 1(2) + 2(4) = 16

and

6 + 1 + 2 = 9

vertices. So

n_1 = 6

Question 9

In a tournament (complete directed graph) on 7 vertices, vertex $v$ has out-degree 5. What is the maximum number of vertices that can be reached from $v$ by a directed path of length exactly 2?

Exactly 4 vertices
Exactly 5 vertices
Exactly 6 vertices
Exactly 2 vertices (correct answer)

Explanation: Since

v

has out-degree 5 in a tournament on 7 vertices,

v

has directed edges to 5 other vertices and in-degree 1. Let

u

be the vertex that beats

v

, and

w_1, w_2, w_3, w_4, w_5

be the vertices that

v

beats. For a path of length exactly 2 from

v

, we need

v → w_i → x

where there's no direct edge

v → x

. Since

v

already beats 5 vertices directly, the only vertices

v

doesn't beat directly are

v

itself and

u

. The vertices reachable in exactly 2 steps are those that some

w_i

beats but

v

doesn't beat directly. These can only be

u

and possibly

v

itself, giving a maximum of 2 vertices.

Question 10

A connected graph $G$ has the property that every vertex lies on at least one cycle. If $G$ has 10 vertices and 15 edges, what is the maximum number of edge-disjoint cycles that $G$ can contain?

5 cycles
6 cycles (correct answer)
3 cycles
4 cycles

Explanation: Since every vertex lies on at least one cycle,

G

contains no cut vertices and is 2-connected. The cycle rank (maximum number of edge-disjoint cycles) equals

m - n + 1

where

m

is the number of edges and

n

is the number of vertices. This gives

15 - 10 + 1 = 6

. This maximum is achievable: we can construct such a graph by taking multiple small cycles that share vertices but have no edges in common, ensuring every vertex lies on some cycle while achieving the theoretical maximum of 6 edge-disjoint cycles.

Question 11

Consider the adjacency matrix $M$ of a simple graph $G$ with 6 vertices. If $(M^3)_{2,5} = 4$ , what can be concluded about the relationship between vertices 2 and 5?

There are exactly 4 distinct paths of length 3 from vertex 2 to vertex 5
There are exactly 4 distinct walks of length 3 from vertex 2 to vertex 5 (correct answer)
Vertices 2 and 5 are connected by exactly 4 edge-disjoint paths
The shortest path from vertex 2 to vertex 5 has length 4

Explanation: The entry

(M^3)_{2,5}

counts the number of walks of length exactly 3 from vertex 2 to vertex 5, where a walk allows repeated vertices and edges. This is exactly 4 walks, not necessarily distinct paths (which cannot repeat vertices). Option A is wrong because paths cannot repeat vertices, while walks can. Option C confuses this with edge-connectivity. Option D incorrectly interprets the matrix power as giving shortest path length rather than walk count.