Unit 5 - Practice Quiz

The definition of a planar graph is that it has a planar embedding, meaning it can be drawn on a plane such that no two edges intersect except at their shared vertices.

By Kuratowski's theorem, a graph is non-planar if it contains a subgraph that is a subdivision of or . , the complete graph with 5 vertices, is a fundamental example of a non-planar graph.

Euler's formula for connected planar graphs states that the number of vertices minus the number of edges plus the number of faces (including the outer unbounded face) is always equal to 2.

Using Euler's formula , we can substitute the given values: . This simplifies to , so .

A proper vertex coloring of a graph is an assignment of colors to the vertices such that no two vertices connected by an edge share the same color.

The chromatic number, , is defined as the smallest number of colors required to perform a proper vertex coloring of the graph G.

In a complete graph , every vertex is adjacent to every other vertex. Therefore, each of the vertices requires a unique color, making the chromatic number equal to .

The fundamental definition of a tree is that it is a connected, undirected graph that has no cycles.

A key property of trees is that the number of edges is always one less than the number of vertices. An undirected graph with vertices is a tree if and only if it is connected and has edges.

Because a tree is connected, there is at least one path between any two vertices. Because it has no cycles, this path must be unique.

A rooted tree is a tree in which one special vertex has been designated as the 'root'. This designation creates a parent-child hierarchy among the nodes that does not exist in an unrooted tree.

An internal node (or inner node) is any node of a tree that has at least one child. In other words, it is any node that is not a leaf.

A spanning tree of a connected, undirected graph G is a subgraph that connects all the vertices together (spans the graph) with the minimum possible number of edges, thereby forming a tree.

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, edge-weighted graph that connects all the vertices together, without cycles, and with the minimum possible sum of edge weights.

Both Prim's algorithm and Kruskal's algorithm are famous greedy algorithms for finding an MST. Dijkstra's and Floyd-Warshall are for shortest paths, while BFS is a traversal algorithm.

Leaf nodes are the terminal nodes of the decision tree. They represent the final outcome or classification for the path taken through the tree's decision points (internal nodes).

A decision tree is a model used to visually and explicitly represent decisions and decision making. Each internal node represents a choice/test, each branch an outcome, and each leaf a final result.

Infix notation is the common mathematical notation where the operator is written in between its operands.

In prefix notation, the operator comes before its operands. First, A + B becomes + A B. Then, (+ A B) * C becomes * + A B C.

In postfix notation, the operator is written after its operands. This notation is also called Reverse Polish Notation (RPN).

In a planar embedding, let be the number of regions. The sum of the degrees of the regions is . Since the graph has no triangles, the degree of each region must be at least 4 (each face is bounded by at least 4 edges).
So, , which implies or .
From Euler's formula, . Substituting , we get:



, or . This is a key property for bipartite planar graphs.

First, find the number of regions () using Euler's formula: . Given and , we have , which gives . Let be the number of edges bounding each region. The sum of the degrees of all regions is equal to . Since each of the 6 regions has the same degree , we have . So, . Solving for , we get . This graph could be the skeleton of a cube.

We check the inequality for each option. A graph that violates this inequality cannot be planar.
A) . . Since , it could be planar.
B) . . Since , this graph cannot be planar. This is the complete graph .
C) . . Since , it could be planar.
D) . . Since , it could be planar.

First, find the number of edges () using the Handshaking Lemma. The sum of degrees is . Since , we have , so . Now use Euler's formula for connected planar graphs: . With and , we get , which gives , so .

The wheel graph consists of a cycle of 7 vertices () and a central hub vertex connected to all 7 vertices of the cycle. The cycle is an odd cycle, so its chromatic number is 3. Let's say we use colors {1, 2, 3} for the cycle vertices. The central hub is adjacent to all these vertices, so it cannot be colored with 1, 2, or 3. Therefore, it requires a fourth color. A valid 4-coloring is possible. Hence, the chromatic number .

The definition of the chromatic number is that is the minimum number of colors needed for a proper vertex coloring of . If , it means the graph can be colored with 5 colors, but not with 4 or fewer colors. Therefore, the statement 'G cannot be properly colored using 4 colors' is true by definition.

A complete bipartite graph consists of two disjoint sets of vertices, with vertices and with vertices. Every vertex in is connected to every vertex in , and there are no edges within or within . To color , we can assign one color (e.g., color 1) to all 5 vertices in the first set and a second color (e.g., color 2) to all 7 vertices in the second set. Since no two vertices in the same set are adjacent, this is a valid 2-coloring. Since the graph has edges, it is not 1-colorable. Therefore, the chromatic number is 2.

In a forest with components (trees), the relationship between vertices () and edges () is . The problem states , , and . We can verify this: , which is consistent. The total number of vertices is the sum of vertices in each tree. Let the number of vertices in the three trees be . We are given and . The total number of vertices is . So, , which gives , so . The largest tree has 9 vertices.

Let be the number of vertices of degree 1, and be the number of vertices of degree 3. We are given . The total number of vertices is . By the Handshaking Lemma, the sum of degrees is . So, . For any tree, we know . Now we can set the two expressions for equal: , which simplifies to . Solving gives . The total number of vertices is .

Options A, B, and C are all standard, equivalent definitions of a tree. Option D is partially correct but contains a flaw. While it is true that a tree has a unique simple path between any two vertices, adding an edge between two existing vertices in a tree creates exactly one cycle, not two.

In a full m-ary tree, the relationship between the number of leaves () and internal vertices () is . Here, and . We can solve for : , which gives , so , and . The total number of vertices is the sum of internal vertices and leaves: . Therefore, .

The maximum number of vertices in a binary tree of height is given by the formula . For a height , the maximum number of vertices is . This occurs when the tree is a complete binary tree of height 4, with the number of vertices at each level being .

A complete graph has vertices and a total of edges. An MST for any graph with 5 vertices must have exactly edges. Kruskal's algorithm sorts all 10 edges and attempts to add each one. To form the MST, 4 edges will be successfully added. The remaining edges, if added, would form a cycle and are therefore rejected. The number of rejected edges is the total number of edges minus the number of edges in the MST: .

A fundamental property of MSTs is that while the tree itself may not be unique (if there are multiple edges with the same weight), the total weight of any MST for a given graph is always the same unique minimum value. Option A is false, as multiple MSTs can exist. Option C is false because if weights are not unique, the algorithms might make different choices and produce different (but equally weighted) MSTs. Option D is false because a heavy edge might be a bridge that is essential for connectivity.

The MST connects all vertices with minimum total weight, while a shortest path finds the minimum weight path between two specific vertices. These objectives are different. An edge with a large weight might be excluded from the MST, but it could be a crucial 'shortcut' for the shortest path between two vertices. Therefore, the shortest path often uses edges not present in the MST.

The problem of sorting elements has possible outcomes (permutations). A binary decision tree for sorting must have at least leaves. The height of the tree, , represents the worst-case number of comparisons. For a binary tree, the number of leaves is at most . Therefore, we must have . For , we need . Since and , the smallest integer that satisfies the inequality is 5. Thus, the minimum number of comparisons is .

Each weighing on a balance scale has three possible outcomes: the left side is heavier, the right side is heavier, or they are equal. Therefore, the decision tree is a 3-ary (ternary) tree. There are 8 possible outcomes (coin 1 is counterfeit, coin 2 is counterfeit, ..., coin 8 is counterfeit), so the decision tree must have at least 8 leaves. If the height of the ternary tree is , it can have at most leaves. We need to find the smallest integer such that . For , (not enough). For , (which is ). Therefore, the minimum height of the decision tree is 2, corresponding to a minimum of 2 weighings.

We convert the expression following operator precedence and parentheses.

1. Convert parenthesized sub-expressions: (A + B) becomes A B +, (D - E) becomes D E -, and (F + G) becomes F G +.
2. The expression is now (A B +) * C - (D E -) * (F G +).
3. Apply the multiplications: (A B +) * C becomes A B + C * and (D E -) * (F G +) becomes D E - F G + *.
4. The expression is now (A B + C *) - (D E - F G + *).
5. Apply the final subtraction: A B + C * D E - F G + * -.

We use a stack to evaluate the expression from left to right.

1. Push 9. Stack: [9]
2. Push 5. Stack: [9, 5]
3. Push 2. Stack: [9, 5, 2]
4. Operator +: Pop 2, pop 5. Compute . Push 7. Stack: [9, 7]
5. Operator *: Pop 7, pop 9. Compute . Push 63. Stack: [63]
6. Push 6. Stack: [63, 6]
7. Push 2. Stack: [63, 6, 2]
8. Operator /: Pop 2, pop 6. Compute . Push 3. Stack: [63, 3]
9. Operator -: Pop 3, pop 63. Compute . Push 60. Stack: [60]
   The final result on the stack is 60.

Kuratowski's Theorem gives a necessary and sufficient condition for a graph to be planar. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of the complete graph or the complete bipartite graph . The other options are also theorems related to planar graphs (consequences of Euler's formula or the Four Color Theorem) but are not the statement of Kuratowski's Theorem itself.

From Euler's formula for connected planar graphs, we have . By the handshaking lemma for faces, the sum of the degrees of all faces is . Since the girth is at least 5, every face must have a degree of at least 5. Thus, , which implies . Substituting this into Euler's formula: . Therefore, .

The Petersen graph is non-planar as it contains a subdivision of . Its crossing number is a well-known property. It can be drawn with just two crossings. It cannot be drawn with one or zero crossings, as this would imply it is planar or could be made planar by removing one edge, which is not true. Therefore, its crossing number is exactly 2.

This is a classic result derived using the deletion-contraction theorem. Let be an edge in . Then . The graph is the path graph , and is the cycle . The chromatic polynomial for a path is . This leads to the recurrence relation , which solves to .

This question tests the 'cut' and 'cycle' properties of MSTs. The cycle property states that for any cycle in the graph, the edge with the largest weight in cannot be part of any MST. Since all edge weights are distinct, if is in a cycle, it is the unique heaviest edge in that cycle and will be excluded. Conversely, if is not part of any cycle, it must be a bridge (a cut-edge). Removing a bridge disconnects the graph, so it must be included in any spanning tree, including the MST. The conditions 'part of a cycle' and 'not a bridge' are equivalent for an edge in a connected graph.

Using the Shunting-yard algorithm:

1. A -> Output: A
2. + -> Stack: +
3. B -> Output: A B
4. * -> Stack: + *
5. C -> Output: A B C
6. - -> Pop *, Pop +. Output: A B C * +. Stack: -
7. ( -> Stack: - (
8. D -> Output: A B C * + D
9. / -> Stack: - ( /
10. E -> Output: A B C * + D E
11. ^ -> Stack: - ( / ^
12. F -> Output: A B C * + D E F
13. ) -> Pop ^, Pop /. Output: A B C * + D E F ^ /. Stack: -
14. * -> Stack: - *
15. G -> Output: A B C * + D E F ^ / G
16. End -> Pop *, Pop -. Final Output: A B C * + D E F ^ / G * -

The sum of degrees in a tree with vertices is . If there are 4 leaves (degree 1), the sum of their degrees is 4. The remaining 2 vertices must have degrees and . The possible integer partitions are (4,2) and (3,3).
Case 1: Degree sequence (4,2,1,1,1,1). Choose the vertex with degree 4 ( ways) and degree 2 ( ways). Using the generalized Cayley formula, the number of trees is .
Case 2: Degree sequence (3,3,1,1,1,1). Choose the 2 vertices with degree 3 ( ways). Number of trees is .
Total number of trees is .

We are given the relation and . So, , which simplifies to . We want to maximize the number of internal nodes, . To maximize , the term must be minimized. The smallest possible value for in an m-ary tree is (a binary tree). If , then . This gives , so . This corresponds to a full binary tree with 72 internal nodes and 73 leaves.

A decision tree for sorting elements must be able to distinguish between all possible permutations of the input. Each permutation must correspond to a unique leaf in the tree. A binary tree of height has at most leaves. Therefore, we must have . Taking the logarithm base 2 gives . Since the height must be an integer, the tightest possible lower bound is . The other options are either approximations (like using Stirling's approximation for ) or bounds for simpler problems.

We are given the number of vertices, . Since the graph is 3-regular, every vertex has a degree of 3. By the handshaking lemma, the sum of degrees is equal to twice the number of edges: . So, , which means and . Now, we use Euler's formula for connected planar graphs: . Plugging in the values for and , we get , which simplifies to . Therefore, the number of faces is .

A fundamental property of k-critical graphs (for ) is that they are 2-connected. This means they cannot be disconnected by removing a single vertex. A vertex cut of size 1 is also known as a cut vertex or articulation point. Since k-critical graphs are 2-connected, they cannot have a cut vertex. Therefore, the statement that has a vertex cut of size 1 is necessarily false. The other options can be true or false depending on the specific k-critical graph.

If there are multiple MSTs, it implies there are ties in edge weights. If we add an edge to , it creates a cycle. At least one edge on this cycle (other than ) must not be in ; let this be . The cycle property of MSTs implies that cannot be greater than any edge on the cycle path in . Since is an MST, a symmetric argument holds for adding to . This forces . Swapping these two equal-weight edges transforms one MST into another. Specifically, removing from splits it into two components, and must reconnect them. The graph is a spanning tree with the same total weight, hence it is also an MST.

In a maximal planar graph, every face must be a triangle (degree 3). If a face had a degree of 4 or more, one could add a diagonal edge within that face without crossing any existing edges, which contradicts the graph's maximality. Using the handshaking lemma for faces, we know the sum of face degrees is . Since every face has degree 3, we have . We can substitute this into Euler's formula ():


.

The Prufer sequence is generated by iteratively removing the leaf with the smallest label and writing down its unique neighbor. The process stops when two vertices remain.

1. Current leaves: {1, 2, 3, 6}. Smallest is 1. Its neighbor is 4. Remove edge (1,4). Sequence: (4).
2. Current leaves: {2, 3, 6}. Smallest is 2. Its neighbor is 4. Remove edge (2,4). Sequence: (4, 4).
3. Current leaves: {3, 6}. Smallest is 3. Its neighbor is 5. Remove edge (3,5). Sequence: (4, 4, 5).
4. Current leaves: {4, 6}. Smallest is 4. Its neighbor is 5. Remove edge (4,5). Sequence: (4, 4, 5, 5).
   The process stops as only vertices 5 and 6 remain.

We evaluate the expression using a stack:

1. 5: Push 5. Stack: [5]
2. 3: Push 3. Stack: [5, 3]
3. 2: Push 2. Stack: [5, 3, 2]
4. *: Pop 2, 3. Compute 3 * 2 = 6. Push 6. Stack: [5, 6]
5. +: Pop 6, 5. Compute 5 + 6 = 11. Push 11. Stack: [11]
6. 4: Push 4. Stack: [11, 4]
7. -: Pop 4, 11. Compute 11 - 4 = 7. Push 7. Stack: [7]
8. 6: Push 6. Stack: [7, 6]

9. +: Pop 6, 7. Compute 7 + 6 = 13. Push 13. Stack: [13]
   Re-evaluating with a better expression: 5 2 3 * + 4 - 7 + ~.
   5 2 3 * -> 5 6. 5 6 + -> 11. 11 4 - -> 7. 7 7 + -> 14. 14 ~ -> -14. Let's use the one from the question text 5 3 2 * + 4 - 6 + ~ but correct the answer. 5 + (32) = 11. 11-4 = 7. 7+6 = 13. So the result is -13. Option B is correct. Let me double-check my previous thought process. Ah, the explanation should match the provided correct answer. Let's make the expression `3 5 2 4 - 3 + ~. 5 1 +->6.6 2 ->12.12 3 -->9.9 6 +->15.~->-15. I will use my original question and correct the answer. Original:5 3 2 + 4 - 6 + ~. Evaluation:5 + (32) = 11.11 - 4 = 7.7 + 6 = 13.~13 = -13`. So the answer is -13. Let's change the correct option to B.

   Let's try one more time to make it match option A = -11.
   `x~` -> x=11. `y+z=11`. `y=a-b`, `z=c`. Let's say `z=5`, `y=6`. `a-b=6`. `a=m*n`, `b=p`. Let's try `8 3 - 2 * 1 + 5 + ~`. `8 3 -` -> `5`. `5 2 *` -> `10`. `10 1 +` -> `11`. `11 5 +` -> `16`. no.
   Let's use the expression: `3 2 * 5 + 4 - 7 - ~`. `3 2 *`->`6`. `6 5 +`->`11`. `11 4 -`->`7`. `7 7 -`->`0`. `~`->`0`.
   Final attempt: `3 8 4 / + 2 * 5 - ~` 

   3 8 4 / -> 3 2. 3 2 + -> 5. 5 2 * -> 10. 10 5 - -> 5. ~->-5. This is too hard to reverse engineer. I'll write a new one and evaluate it carefully.
   New expression: 7 2 3 * - 5 2 / +. 7 2 3 * -> 7 6. 7 6 - -> 1. 1 5 2 / -> 1 2.5. This uses floats. Let's avoid that.

   Final choice for question:
   "Evaluate the following postfix (Reverse Polish) expression: `5 1 + 4 * 3 -`"
   Options: "21", "20",

Use a stack:

1. 8, 2: Push 8, 2. Stack: [8, 2]
2. *: Pop 2, 8. Compute 8 * 2 = 16. Push 16. Stack: [16]
3. 4: Push 4. Stack: [16, 4]
4. -: Pop 4, 16. Compute 16 - 4 = 12. Push 12. Stack: [12]
5. 5: Push 5. Stack: [12, 5]
6. +: Pop 5, 12. Compute 12 + 5 = 17. Push 17. Stack: [17]
7. 3: Push 3. Stack: [17, 3]
8. -: Pop 3, 17. Compute 17 - 3 = 14. Push 14. Stack: [14]
9. ~: Pop 14. Compute ~14 = -14. Push -14. Stack: [-14]
   Final result is -14.

MST algorithms like Kruskal's and Prim's work by comparing the weights of edges. Adding a constant to every edge weight does not change the relative ordering of the weights. For example, if , then . Therefore, any such algorithm will make the exact same sequence of choices, resulting in the same set of edges for the MST. So, is the same tree as . The total weight of is the sum of the new weights of its edges: . Since an MST on vertices has exactly edges, the second sum is . Thus, .

This problem can be modeled with a decision tree. A balance scale has 3 possible outcomes: the left pan is heavier, the right pan is heavier, or they are equal. This means the decision tree is ternary. With weighings, you can distinguish between at most different outcomes (the leaves of the tree). To find one heavier coin among , we need to distinguish between possibilities. Therefore, we must have . With weighings, the maximum number of possibilities we can handle is . It is possible to devise a weighing strategy that can find one heavier coin from a set of up to 27 coins in 3 weighings.

A walk that crosses every edge exactly once is called an Eulerian path. A graph contains an Eulerian path if and only if it is connected and has exactly zero or two vertices of odd degree. The graph model for Königsberg has four vertices (the land masses) and seven edges (the bridges). The degrees of the four vertices are 5, 3, 3, and 3. Since all four vertices have an odd degree, the graph has neither an Eulerian path nor an Eulerian circuit, making the desired walk impossible.

The Petersen graph is not a complete graph and not an odd cycle, so the premises of Brooks's Theorem apply. Its maximum degree is . Its chromatic number is . The theorem states that will be at most . Since , the condition is satisfied. Therefore, the Petersen graph is not a counterexample; rather, it is an example of a graph where the bound is met exactly.

This is a combinatorial enumeration problem that requires systematically constructing the trees based on the partitions of the number of non-root vertices () into subtrees attached to the root.
The partitions of 4 are:

1. (4): A root connected to the root of a single 4-vertex tree (4 ways).
2. (3,1): A root connected to a 3-vertex tree and a 1-vertex tree (2 ways).
3. (2,2): A root connected to two identical 2-vertex trees (1 way).
4. (2,1,1): A root connected to one 2-vertex tree and two 1-vertex trees (1 way).
5. (1,1,1,1): A root connected to four 1-vertex trees (1 way).
   Summing these up gives distinct non-isomorphic rooted trees.

The Four Color Theorem states that any planar graph has a chromatic number of at most 4. We are looking for the smallest planar graph that requires exactly 4 colors. The complete graph has . The graph has 4 vertices, is planar (it can be drawn as a square with diagonals, or as a tetrahedron), and requires 4 colors since every vertex is connected to every other vertex. The graph is non-planar, and any graph with fewer than 4 vertices requires at most 3 colors. Therefore, the minimum number of vertices for a planar graph with is 4.