Graph Theory - Homework

1. Which one of the following graphs is planar?

a) b) c) d) only the first two graphs e) all three graphs

2. Apply Prim’s algorithm to obtain a minimum spanning tree for the network shown, what’s the total weight
of this tree?
a) 15
b) 16
c) 17
d) 18
e) None
3. Which of the following graphs are trees?

a) A, B, C
b) A, B, D
c) A, B, D, F
d) A, B, D, E
e) None
4. For which one of the following graphs is the sum of the degrees of the vertices equal to 14?

5. For the graph on the right, the sum of the degrees of the vertices is:
a) 22
b) 23
c) 24
d) 25
e) 26

6. The length of the shortest path from F to B in the network shown is:
a) 17
b) 18
c) 19
d) 20
e) 21
7. Which one of the following graphs is a spanning tree for the network shown on the right?

8. How many edges are there in a tree with 15 vertices?

a) 14
b) 15
c) 16
d) 17
e) 18
9. How many vertices are there in a tree with 5 edges?
a) 4
b) 5
c) 6
d) 7
e) 8
0 1 0 1
1 0 1 0
10. The graph that matches the matrix � � is:
0 1 0 1
1 0 1 0

11. The minimum number of edges for a graph with seven vertices to be connected is:
a) 4
b) 5
c) 6
d) 7
e) 21
12. A complete graph with six vertices is drawn. This network would best represent:
a) the journey of a paper boy who delivers to six homes covering the minimum distance
b) the cables required to connect six houses to a pay television service that minimizes the length of
cables needed
c) a six-team basketball competition where all teams play each other once
d) a project where six tasks must be performed between the start and finish
e) the allocation of different assignments to a group of six students
13. Disconnected components can be created in case of:
a) undirected graphs
b) subgraphs
c) disconnected graphs
d) complete graphs
e) cycle graphs

14. A simple graph can have:

a) multiple edges
b) self-loops
c) parallel edges
d) no multiple edges, self-loops, and parallel edges
e) None

15. G is an undirected graph with 𝑛𝑛 vertices and 26 edges such that each vertex of G has a degree at least 4.
Then the maximum possible value of 𝑛𝑛 is
a) 7
b) 6
c) 13
d) 10
e) None

16. The maximum number of edges in a bipartite graph on 14 vertices is:

a) 56
b) 14
c) 49
d) 87
e) None

17. Which one is the expression 𝑎𝑎/𝑏𝑏 + 𝑐𝑐 ∗ 𝑑𝑑 − 𝑒𝑒 in postfix notation?

a) 𝑎𝑎𝑎𝑎 + 𝑐𝑐𝑐𝑐/∗ −𝑒𝑒
b) 𝑎𝑎𝑎𝑎/𝑐𝑐𝑐𝑐 ∗ +𝑒𝑒 −
c) 𝑎𝑎𝑎𝑎𝑎𝑎/+𝑑𝑑 ∗ −𝑒𝑒
d) 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎/+ ∗ −𝑒𝑒
e) None

18. Which one is the expression 4 ∗ 5 + 3/2 − 9 in prefix notation?

a) ∗ 45 −/32 + 9
b) ∗ +453/−29
c) − +∗ 45/329
d) ∗ +/45932
e) None

19. If 10 people each shake hands with each other, how many handshakes took place?
a) 90
b) 45
c) 9
d) 10
e) 100

20. Among a group of 5 people, it is possible for everyone to be friends with exactly 3 of the people in the
group.
a) True
b) False
21. The graph below is bipartite:
a) True
b) False
22. Any induced subgraph of a complete graph is also complete.
a) True
b) False

23. Which one must be a degree sequence for a tree?

24. The graph G has 6 vertices with degrees 5, 4, 4, 3, 2, 2. G could be a planar graph.
a) True
b) False

25. The Petersen graph (below) is not planar.

a) True
b) False

26. At a school dance, 6 girls and 4 boys take turns dancing (as couples) with each other.
How many couples danced if every girl dances with every boy?
a) 24
b) 10
c) 90
d) 45
e) 12

27. What graph can be used to represent the situation explained in the previous question?
a) 𝐾𝐾10
b) 𝐾𝐾10,10
c) 𝐾𝐾4,6
d) 𝐶𝐶10
e) 𝑃𝑃10

28. What’s the number of connected components for the following graph?
a) 1
b) 2
c) 3
d) 4
e) 5

29. What is the total degree of a tree with n vertices?

a) n
b) n-1
c) 2n-1
d) 2n-2
e) None
30. how many paths are there from b to f?
a) 3
b) 4
c) 5
d) 6
e) 7

31. How many connected subgraphs of G have four vertices and include a cycle?
a) 2
b) 3
c) 4
d) 5
e) 6

32. How many connected spanning subgraphs are there in the graph G in the previous question?
a) 2
b) 3
c) 4
d) 5
e) 6

33. The following graph is bipartite.

a) True
b) False

34. An undirected graph 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) where |𝑉𝑉| = |𝐸𝐸| + 1, 𝐺𝐺 could be:
a) A tree
b) A disconnected graph
c) A cyclic graph
d) A path
e) All

35. Let 𝑇𝑇 = (𝑉𝑉, 𝐸𝐸) be a tree with |𝑉𝑉| = 𝑛𝑛 ≥ 2. How many distinct paths are there (as subgraphs) in T?
a) n
b) n-1
c) C(n,2)
d) P(n,2)
e) 𝑛𝑛2

36. Write the expression 𝑡𝑡 + (𝑢𝑢 ∗ 𝑣𝑣)/(𝑤𝑤 + 𝑥𝑥 − 𝑦𝑦 ∗ 𝑧𝑧) in Polish notation without parentheses (no space
between characters, instead of * use x for multiplication, e.g., instead of 3*4, write down 3x4).

37. What is the value of the expression (in Polish notation) ⁄↑ 𝑎𝑎 − 𝑏𝑏𝑏𝑏 + 𝑑𝑑 ∗ 𝑒𝑒𝑒𝑒, if 𝑎𝑎 = 𝑐𝑐 = 𝑑𝑑 = 𝑒𝑒 = 2, and
𝑏𝑏 = 𝑓𝑓 = 4?
a) 32
b) 2.5
c) 0.4
d) 2
e) None
38. For the tree shown in below, list the vertices according to a preorder traversal (no comma, no space).

39. For the tree shown in question 38, list the vertices according to an inorder traversal (no comma, no space).

40. For the tree shown in question 38, list the vertices according to a postorder traversal (no comma, no space).

41. The depth-first spanning tree for the graph shown in below is (the order of the vertices is given as
alphabetical order):

a) b) c) d)

42. The breadth-first spanning tree for the graph shown in the previous question is (the order of the vertices is
given as alphabetical order):

a) b) c) d)

43. Apply Kruskal's algorithm to the graph shown in the following graph, what’s the weight of the resulting
tree?
a) 16
b) 17
c) 18
d) 19
e) None
44. There is a graph with 31 vertices. The maximum degree of this graph is 3. What could be the maximum
number of edges in this graph?
a. 33
b. 34
c. 45
d. 46
e. None

45. 𝐺𝐺 is a 𝑘𝑘-regular graph with 105 edges. 𝑘𝑘 cannot be:

a. 3
b. 5
c. 7
d. 9
e. All

46. 𝐺𝐺 is a simple graph with 4 vertices and 5 edges. The adjacency matrix of 𝐺𝐺 has -------- non-zero entries.
a. 4
b. 6
c. 8
d. 10
e. None

47. 𝐺𝐺 is a simple graph with 5 vertices and the adjacency matrix of 𝐺𝐺 has 5 zero entries. 𝐺𝐺 is a:
a. Cycle
b. Tree
c. Complete graph
d. Bipartite graph
e. Planar graph

48. 𝐺𝐺 is a simple graph with more than 3 vertices. 𝐴𝐴 is the adjacency of 𝐺𝐺, and all entries on the diagonal of the
matrix 𝐴𝐴2 are the same number. As a result:
a. 𝐺𝐺 is not a complete graph
b. The minimum degree of 𝐺𝐺 is 1
c. The maximum degree of 𝐺𝐺 is greater than the minimum degree of 𝐺𝐺
d. The maximum degree of 𝐺𝐺 equals to the minimum degree of 𝐺𝐺
e. 𝐺𝐺 is not a cycle

49. The adjacency matrix of a graph is , what is the first row of the distance matrix for
this digraph?
a. 0, 1, 2, 3, 2
b. 0, 1, 4, 3, 2
c. 0, 1, 3, 2, 2
d. 0, 1, 3, 3, 2
e. None

50. If you add up all the elements in the first row of the distance matrix for the digraph below, the answer is:

a. 5
b. 6
c. 7
d. 8
e. 9