Unit 5: Graphs Theory II - Practice Quiz

1 What is a planar graph?

2 Which complete graph is non-planar?

3 For a connected planar graph with vertices, edges, and faces, Euler's formula is:

4 A connected planar graph has vertices and edges. How many faces does it have?

5 What is a proper vertex colouring of a graph?

6 What does the chromatic number of a graph represent?

7 What is the chromatic number of a nonempty bipartite graph?

8 Which statement defines a tree graph?

9 How many edges does a tree with vertices have?

10 How many simple paths exist between any two distinct vertices of a tree?

11 What is the specially designated vertex of a rooted tree called?

12 What is a leaf in a rooted tree?

13 What must a spanning tree of a connected graph include?

14 What is a minimum spanning tree of a connected weighted graph?

15 Which algorithm is commonly used to find a minimum spanning tree?

16 In a decision tree, what does an internal node usually represent?

17 In a decision tree, what does a leaf node usually represent?

18 Which expression is written in infix notation?

19 What is the prefix form of the infix expression ?

20 What is the postfix form of the infix expression ?

21 A simple connected planar graph has vertices. What is the maximum possible number of edges it can have?

22 Why can the complete bipartite graph not be planar?

23 A connected planar graph has vertices and edges. How many faces does a planar embedding of the graph have, including the outer face?

24 A connected planar graph has vertices, and every face is bounded by exactly three edges. How many faces does it have?

25 What is the chromatic number of the cycle graph ?

26 What is the chromatic number of the complete bipartite graph ?

27 A graph has chromatic number . A new vertex is added and connected to every vertex of . What is the chromatic number of the resulting graph?

28 A connected graph with vertices contains no cycles. How many edges does it have?

29 A forest has vertices and connected components. How many edges does the forest contain?

30 A tree has three vertices of degree , four vertices of degree , and all remaining vertices are leaves. How many leaves does the tree have?

31 What is the maximum number of vertices in a binary rooted tree of height , where the root is at level ?

32 A full binary rooted tree has internal vertices. How many leaves does it have?

33 In a rooted tree, the root has children and . Vertex has child , and vertex has child . What is the lowest common ancestor of and ?

34 How many distinct spanning trees does the cycle graph have?

35 A weighted graph has edges , , , , , , and . What is the weight of a minimum spanning tree?

36 A connected weighted graph has a different weight on every edge. Which statement is guaranteed to be true?

37 A binary decision tree must distinguish among possible outcomes. What is the minimum possible height in the worst case?

38 Using a comparison-based decision tree, what is the minimum number of comparisons required in the worst case to find the maximum among distinct elements?

39 Which postfix expression is equivalent to the infix expression ?

40 What is the value of the prefix expression ?

41 A connected simple planar graph has vertices and edges. In any planar embedding of this graph, how many faces have boundary length exactly ?

42 A planar embedding of a graph has vertices, edges, and connected components. Counting the unbounded face only once, how many faces does the embedding have?

43 A simple planar graph has vertices and girth at least . What is the largest integer upper bound on its number of edges implied by the planar girth inequality?

44 A connected plane graph has vertices, edges, and exactly bridges. Which description of its planar dual is correct?

45 Let be the wheel obtained by joining one hub to every vertex of the cycle . If one rim edge is deleted while all spokes remain, what is the chromatic number of the resulting graph?

46 The join is formed from disjoint graphs and by adding every edge between their vertex sets. What is ?

47 A graph is obtained by subdividing every edge of exactly once, using a different new vertex on each edge. What is ?

48 The vertices of the line graph represent the edges of , with adjacency defined by sharing an endpoint. What is ?

49 A tree has vertices. Exactly vertices have degree , exactly have degree , and every remaining vertex has degree or . How many leaves does the tree have?

50 A fixed forest on labeled vertices has four tree components of orders , , , and . How many labeled spanning trees on the same vertices contain every edge of this forest?

51 An ordered binary tree has preorder traversal and inorder traversal . What is its postorder traversal?

52 A rooted tree has vertices. Exactly vertices have one child, exactly vertices have three children, and every other internal vertex has two children. How many leaves does the tree have?

53 How many spanning trees of the labeled complete graph contain a particular fixed edge?

54 A weighted graph has vertices and edges , , , , , and . How many distinct minimum spanning trees does it have?

55 In with vertices , assign edge the weight . How many distinct minimum spanning trees exist?

56 In the comparison decision-tree model, what is the information-theoretic lower bound on the worst-case number of comparisons needed to sort distinct elements?

57 Two sorted lists contain and distinct elements, respectively. If every relative interleaving is possible, what information-theoretic lower bound does a binary comparison decision tree give for merging them?

58 Assuming every operator is binary, which infix expression corresponds to the prefix expression ?

59 What is the postfix form of ?

60 Assuming all operators are binary, which fully parenthesized infix expression is represented by the postfix expression ?