Timedora
Free Practice Quiz Question List

11 Graph Properties and Applications Online Quiz Questions

Use this free practice quiz with 20 questions to review 11 Graph Properties and Applications, test your knowledge, and prepare for your next test or exam.

20 questions
01
Choose one
1 point

A connected undirected graph has exactly four vertices of odd degree. Which conclusion follows?

  1. A

    It has an Eulerian circuit.

  2. B

    It has neither an Eulerian path nor an Eulerian circuit.

  3. C

    It has an Eulerian path but not an Eulerian circuit.

  4. D

    The degree information is insufficient because Eulerian paths depend only on vertices.

02
True or false
1 point

A Hamiltonian path and an Eulerian path have the same defining requirement: each must use every edge exactly once.

  1. A

    True

  2. B

    False

03
Written response
1 point

What is the chromatic number of an odd cycle?

04
Fill in the blank
1 point

In Hall’s marriage theorem, the set of vertices in the opposite part adjacent to at least one vertex of SS is called the of SS.

05
Choose one
1 point

A simple connected planar graph has eight vertices. Which is the greatest number of edges allowed by the standard planar bound?

  1. A

    14

  2. B

    16

  3. C

    18

  4. D

    24

06
Choose all
1 point

Select all applications that are most naturally modeled by vertex coloring or an Eulerian route.

  1. A

    Inspect every road.

  2. B

    Visit every city exactly once.

  3. C

    Schedule exams with shared students at different times.

  4. D

    Pair every participant exactly once.

07
Fill in the blank
1 point

A matching to which no additional edge can be added is called .

08
True or false
1 point

Every maximal matching in a graph is necessarily a maximum matching.

  1. A

    True

  2. B

    False

09
Written response
1 point

A connected plane graph has six vertices and eight edges. How many faces does it have, including the unbounded exterior face?

10
Choose one
1 point

A bipartite graph has parts of sizes five and three. What can be concluded about the existence of a Hamiltonian path?

  1. A

    It is guaranteed because both parts are nonempty.

  2. B

    It cannot exist because the part sizes differ by more than one.

  3. C

    It can exist only if the graph is planar.

  4. D

    It is guaranteed if every vertex has degree at least two.

11
Choose all
1 point

Select all statements that are correct about planar graphs or planar bipartite graphs.

  1. A

    For a simple connected planar bipartite graph, ∣E∣≤2∣V∣−4|E|\le 2|V|-4 under the stated conditions.

  2. B

    Every drawing of a planar graph must be crossing-free.

  3. C

    K3,3K_{3,3} is nonplanar because its nine edges exceed the planar bipartite bound for six vertices.

  4. D

    A graph is nonplanar whenever one drawing of it contains a crossing.

12
Open ended
1 point

A university must schedule examinations so that two examinations sharing a student are not held at the same time. Explain how to model this situation as a graph-coloring problem and what the chromatic number represents.

13
Choose one
1 point

Three students have project preferences A:{1,2}A:\{1,2\}, B:{2,3}B:\{2,3\}, and C:{1,3}C:\{1,3\}. The assignments A→1A\to1, B→2B\to2, and C→3C\to3 form which kind of matching?

  1. A

    It is maximal but not maximum.

  2. B

    It is a perfect matching.

  3. C

    It is an Eulerian circuit in the assignment graph.

  4. D

    It violates Hall’s condition because project 3 is used.

14
Choose one
1 point

A connected undirected graph has vertex degrees 3, 2, 4, 3, and 2. Which conclusion follows?

  1. A

    An Eulerian circuit but no Eulerian path

  2. B

    An Eulerian path but no Eulerian circuit

  3. C

    Neither an Eulerian path nor an Eulerian circuit

  4. D

    Both an Eulerian path and an Eulerian circuit

15
Choose one
1 point

A street-sweeping crew wants to traverse every road in a neighborhood, with roads represented by edges. Which graph problem most directly models this requirement?

  1. A

    A Hamiltonian path problem

  2. B

    A vertex-coloring problem

  3. C

    An Eulerian route problem

  4. D

    A matching problem

16
Choose one
1 point

In an examination schedule, each vertex represents an exam and an edge joins exams that share students. What graph operation assigns time slots so that conflicting exams are not simultaneous?

  1. A

    Assigning colors to vertices

  2. B

    Finding a Hamiltonian cycle

  3. C

    Finding a perfect matching

  4. D

    Counting faces in a plane embedding

17
True or false
1 point

True or false: Every maximal matching in a graph is also a maximum matching.

  1. A

    True

  2. B

    False

18
Choose one
1 point

A connected plane graph has ∣V∣=6|V|=6 vertices and ∣E∣=9|E|=9 edges. How many faces, including the exterior face, does it have?

  1. A

    4

  2. B

    5

  3. C

    6

  4. D

    7

19
Written response
1 point

What is the greatest number of edges allowed by the bipartite planar bound for a simple connected bipartite planar graph with 6 vertices?

20
Written response
1 point

What theorem gives a necessary and sufficient condition for a bipartite graph to have a matching that covers every vertex in a specified part?