Processing math: 100%

Skills Check

Skills Check

Question 1.1

1. The accompanying graph has

image
  1. four vertices and six edges.
  2. four vertices and four edges.
  3. five vertices and six edges.

1.

c

Question 1.2

2. The number of vertices in the following graph is ____, while the number of edges in this graph is ______.

image

2.

7; 9

Page 24

Question 1.3

3. The accompanying graph

image
  1. is even-valent.
  2. is not connected.
  3. has six components.

3.

b

Question 1.4

4. The graph shown below is not connected because it consists of _______ parts.

image

4.

four

Question 1.5

5. What is the valence of vertex B in the graph below?

image
  1. 2
  2. 1
  3. 3

5.

a

Question 1.6

6. A graph has 24 edges and all the vertices of the graph have valence 3. The number of vertices of the graph must be ______.

6.

16

Question 1.7

7. The valences of the vertices in the accompanying graph, listed in decreasing order, are

image
  1. 6, 4, 3, 3, 3, 2, 1, 1, 1.
  2. 1, 3, 4, 4, 5, 5.
  3. 5, 5, 4, 3, 3, 1, 1, 1.

7.

a

Question 1.8

8. The alphabetically ordered list of even-valent vertices of the graph below is ______, ______.

image

8.

B; E

Question 1.9

9. Which of the statements about the accompanying graph is false?

  1. It is connected.
  2. It is not a graph because it includes curved edges.
  3. It is even-valent.
image

9.

c

Question 1.10

10. The accompanying graph has _____ edges and ______ vertices.

image

10.

8; 7

Page 25

Question 1.11

11. Which of the following statements about a path is true?

  1. A path always forms a circuit.
  2. A path is always connected.
  3. A path can visit any vertex only once.

11.

b

Question 1.12

12. A graph G has 10 edges, and all its vertices have the same valence. The possible valences of the vertices of G are _____, _____, _____, _____, _____.

12.

1; 2; 4; 5; 10

Question 1.13

13. It is not possible for a graph to have three vertices of valence 3 and six vertices of valence 4 because

  1. there are no graphs with exactly 11 vertices.
  2. a graph cannot have an even number of 4-valent vertices.
  3. a graph cannot have an odd number of odd-valent vertices.

13.

c

Question 1.14

14. If a graph consists of five vertices and every pair of vertices is connected by a single edge, the number of edges in the graph is exactly _______.

14.

10

Question 1.15

15. For which of the situations below is it most desirable to find an Euler circuit or an efficient eulerization of the graph?

  1. Sweeping the sidewalks of a small town
  2. Planning a new highway
  3. Planning a parade route in Muncie, Indiana

15.

a

Question 1.16

16. For the accompanying graph, the vertex that has the largest valence is _______, and the number of edges in the graph is _______.

image

16.

9; 23

Question 1.17

17. The following graph has no Euler circuit because it

image
  1. is even-valent.
  2. has seven vertices.
  3. is not connected.

17.

c

Question 1.18

18. If a graph is connected and has nine vertices, the graph must have at least _______ edges.

18.

8

Question 1.19

19. Consider the path represented by the sequence of numbered edges on the graph below. Which statement is correct?

image
  1. The sequence of numbered edges forms an Euler circuit.
  2. The sequence of numbered edges forms a circuit but not an Euler circuit.
  3. The sequence of numbered edges traverses each edge exactly once but is not an Euler circuit.

19.

c

Question 1.20

20. The accompanying graph has no Euler circuit because it

image
  1. is not even-valent.
  2. has 16 edges.
  3. is not connected.

20.

a

Page 26

Question 1.21

21. The minimum number of edges that must be duplicated to create a best possible eulerization of the following graph is ______.

image

21.

4

Question 1.22

22. For the accompanying graph, the minimum total number of edges which constitutes a tour of the graph, starting and ending at the same vertex, and which visits each edge at least once, is _______.

image

22.

12

Question 1.23

23. Suppose each vertex of a graph represents a baseball team and each edge represents a game played by two baseball teams. If the resulting graph is not connected, which of the following statements must be true?

  1. At least one pair of teams never played a game.
  2. At least one team played every other team.
  3. The teams play in distinct leagues.

23.

a

Question 1.24

24. If a graph has eight vertices of odd valence, the absolute minimum number of edges that must be added (duplicated) to eulerize the graph is ______.

24.

4

Question 1.25

25. Suppose the edges of a graph represent streets that must be salted after a snowstorm. To eulerize the graph, four edges must be added. The real-world interpretation of this is that

  1. four streets will be traversed twice.
  2. four streets will not be salted.
  3. four new streets would be built.

25.

a

Question 1.26

26. For each of the following situations, decide whether a graph or a digraph seems a more reasonable model.

  1. A system of hiking trails: ___________
  2. A bus route map: ___________
  3. An electrical wiring plan for a home: _________

26.

digraph; digraph; graph

Question 1.27

27. The smallest number of edges needed to eulerize the graph below is

image
  1. 4.
  2. 6.
  3. 8.

27.

b

Question 1.28

28. If the valences of the vertices of a graph G are: 5, 4, 4, 4, 4, 3, 2, 2, and 2, the number of vertices of G is _______ and the number of edges of G is _______.

28.

9; 15

Question 1.29

29. The smallest number of edges that must be added to the accompanying graph for it to have an Euler circuit is

image
  1. 3.
  2. 6.
  3. 7.

29.

a

Question 1.30

30. The number of edges in a Chinese postman tour (i.e., a tour with a minimum number of edges that starts and ends at the same vertex and visits each edge at least once) for the accompanying graph is ________.

image

30.

13

[Leave] [Close]