Degrees, paths, cycles, and connectivity - Discrete Math

1. 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$?
   Answer: 6 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$.
2. 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$?
   Answer: 6 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.
3. 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?
   Answer: 2 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.
4. 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?
   Answer: 3 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.
5. 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?
   Answer: 6 cycles 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.
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?
   Answer: $G$ contains a vertex cut of size 2 but no smaller vertex cut exists 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.
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?
   Answer: 12 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.
8. 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?
   Answer: 2 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.
9. 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?
   Answer: At most one pair among $a$, $b$, $c$, $d$ can be connected by a path not involving $v$ 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.
10. 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?
    Answer: Exactly 2 vertices 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.
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?
    Answer: There are exactly 4 distinct walks of length 3 from vertex 2 to vertex 5 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.

Start this quiz