Question

Write down true (T) or false (F) for each statement. Statements are shown below

If a graph with n vertices is connected, then it must have at least n − 1 edges.

If a graph with n vertices has at least n − 1 edges, then it must be connected.

If a simple undirected graph with n vertices has at least n edges, then it must contain a cycle.

If a graph with n vertices contain a cycle, then it must contain at least n edges.

The number of proper vertex colorings (with black and white) of any bipartite graph is at most 2.

If every vertex of a graph has even degree, then the graph has an Euler tour.

There is always a (directed) Hamiltonian cycle in a tournament graph.

In a directed graph G, suppose for any two vertices u and v, there is either a directed path from u to v, or a directed path from v to u (or both can happen). Then, the graph G is strongly connected.

If a simple undirected graph has an Euler tour, then it has a Hamiltonian cycle.

If a simple undirected graph has a Hamiltonian cycle, then it has an Euler tour.

Answer 1

Answers:

1) T-True

2) T-True

3) T - True

4) T - True

5) F - False

6) T - True

7) T - True

8) T - True

9) T - True

10) F - False