Page | 1
C959 DISCRETE MATH I BRAND NEW
2026\2027 ACTUAL EXAM WITH ANSWERS.
1. An undirected graph is this if it remains connected after any
k-1 edges are removed from the graph - correct answer -k-
edgeconnected
2. Of a graph, is the largest k such that the graph is k-
edgeconnected - correct answer -Edge connectivity
3. An undirected graph that is connected and has no cycles -
correct answer -Tree
4. No particular organization of the vertices and edges of a tree
- correct answer -Free tree
5. Vertex at the top is the root and remaining vertices are
arranged according to distance from the root - correct
answer Rooted tree
, Page | 2
6. Vertex at the top of a rooted tree - correct answer -Root
7. Of a vertex is its distance to the root - correct answer -Level
8. Of a tree, is the highest level of any vertex - correct answer
Height
9. Of a vertex v, is the first vertex after v encountered along
path from v to the root - correct answer -Parent
10. Every vertex along the path from v to the root, except for v
itself is this of v - correct answer -Ancestor
11. If v is the parent of vertex u, then u is considered this of
vertex v - correct answer -Child
12. If u is an ancestor v, then v is this of u - correct answer
Descendant
, Page | 3
13. A vertex which has no children - correct answer -Leaf
14. Two vertices are this if they have the same parent - correct
answer -Siblings
15. Rooted at vertex v is the tree consisting of v and all v's
descendants - correct answer -Subtree
16. A vertex of degree 1 - correct answer -Leaf (free trees)
17. If the vertex has degree at least 2 it is considered this -
correct answer -Internal vertex
18. A graph that has no cycles and is not necessarily connected
- correct answer -Forest
, Page | 4
19. The process of systematically visiting each vertex of a tree
to do something with the information stored in the vertices -
correct answer -Traversal
20. A vertex is visited before its descendants - correct answer
Pre-order traversal
21. A vertex is visited after its descendants - correct answer
Post-order traversal
22. Of a connected graph G, it is a subgraph of G which
contains all vertices i G and is a tree - correct answer
Spanning tree
23. Common method for finding spanning trees in a graph,
explores graphs by distance from initial vertex, neighbors
then neighbors of neighbors - correct answer -Breadth-first
search (BFS)
C959 DISCRETE MATH I BRAND NEW
2026\2027 ACTUAL EXAM WITH ANSWERS.
1. An undirected graph is this if it remains connected after any
k-1 edges are removed from the graph - correct answer -k-
edgeconnected
2. Of a graph, is the largest k such that the graph is k-
edgeconnected - correct answer -Edge connectivity
3. An undirected graph that is connected and has no cycles -
correct answer -Tree
4. No particular organization of the vertices and edges of a tree
- correct answer -Free tree
5. Vertex at the top is the root and remaining vertices are
arranged according to distance from the root - correct
answer Rooted tree
, Page | 2
6. Vertex at the top of a rooted tree - correct answer -Root
7. Of a vertex is its distance to the root - correct answer -Level
8. Of a tree, is the highest level of any vertex - correct answer
Height
9. Of a vertex v, is the first vertex after v encountered along
path from v to the root - correct answer -Parent
10. Every vertex along the path from v to the root, except for v
itself is this of v - correct answer -Ancestor
11. If v is the parent of vertex u, then u is considered this of
vertex v - correct answer -Child
12. If u is an ancestor v, then v is this of u - correct answer
Descendant
, Page | 3
13. A vertex which has no children - correct answer -Leaf
14. Two vertices are this if they have the same parent - correct
answer -Siblings
15. Rooted at vertex v is the tree consisting of v and all v's
descendants - correct answer -Subtree
16. A vertex of degree 1 - correct answer -Leaf (free trees)
17. If the vertex has degree at least 2 it is considered this -
correct answer -Internal vertex
18. A graph that has no cycles and is not necessarily connected
- correct answer -Forest
, Page | 4
19. The process of systematically visiting each vertex of a tree
to do something with the information stored in the vertices -
correct answer -Traversal
20. A vertex is visited before its descendants - correct answer
Pre-order traversal
21. A vertex is visited after its descendants - correct answer
Post-order traversal
22. Of a connected graph G, it is a subgraph of G which
contains all vertices i G and is a tree - correct answer
Spanning tree
23. Common method for finding spanning trees in a graph,
explores graphs by distance from initial vertex, neighbors
then neighbors of neighbors - correct answer -Breadth-first
search (BFS)
