Connected graphs chapter 10.4

What is a connected graph?

• A graph where there is a path between every pair of vertices.

• A graph that contains no cycles.

• A graph where each vertex has the same degree.

• A graph that can be drawn without lifting the pencil from the paper.

What is an Eulerian circuit?

• A path that visits every vertex exactly once.

• A path that visits every edge exactly once.

• A circuit that visits every vertex exactly once.

• A circuit that visits every edge exactly once without repeating.

Which condition must be true for a connected graph to have an Eulerian circuit?

• Every vertex has an odd degree.

• Every vertex has an even degree.

• The graph has exactly two vertices of odd degree.

• The graph is complete.

What is a Hamiltonian path?

• A path that visits every vertex exactly once.

• A path that visits every edge exactly once.

• A circuit that visits every vertex exactly once.

• A circuit that visits every edge exactly once.

Which of the following statements is true for all Hamiltonian circuits?

• They are also Eulerian circuits.

• They visit every edge exactly once.

• They visit every vertex exactly once and return to the starting vertex.

• They can only exist in complete graphs.

What is the difference between a walk and a path in graph theory?

• A walk can repeat vertices and edges, while a path cannot repeat vertices or edges.

• A walk cannot repeat vertices or edges, while a path can repeat vertices but not edges.

• A walk and a path are the same in graph theory.

• A walk can repeat edges but not vertices, while a path can repeat vertices but not edges.

What is a trail in graph theory?

• A walk that does not repeat edges but can repeat vertices.

• A walk that does not repeat vertices or edges.

• A path that only visits vertices of even degree.

• A circuit that visits every edge exactly once.

In a graph, if a Hamiltonian path exists, which of the following must also exist?

• An Eulerian circuit

• An Eulerian path

• A connected graph

• A complete graph

Which graph is guaranteed to have both an Eulerian circuit and a Hamiltonian circuit?

• A complete graph of five vertices.

• A graph where all vertices have an odd degree.

• A graph with exactly two vertices of odd degree.

• A graph where all vertices have an even degree and the graph is connected.

What is the necessary condition for a graph to have a Hamiltonian circuit?

• The graph must be complete.

• Every vertex must have an even degree.

• The graph must have no vertices of odd degree.