Solution

The correct answer is Option 4) 4

Key Points

• Statement P: There exists no simple, undirected, and connected graph with 80 vertices and 77 edges.
  • This is true. A simple, undirected, and connected graph with 'n' vertices must contain at least 'n-1' edges to be connected. However, with exactly 'n-1' edges, the graph would be a tree with no cycles. Adding further edges would introduce cycles (assuming we’re considering simple graphs -- that is, no loops or multiple edges). A graph with 80 vertices would require at least 79 edges to be connected, so it's not possible to have a simple, undirected, and connected graph with 80 vertices and 77 edges.
• Statement Q: All vertices of an Euler graph are of even degree.
  • This is true. An Eulerian graph is one where every vertex has an even degree. This condition is both necessary and sufficient for the graph to have an Eulerian cycle (a cycle that covers every edge exactly once).
• Statement R: Every simple, undirected, connected, and acyclic graph with 50 vertices has at least two vertices of degree one.
  • This is true. Such a graph with 'n' vertices is called a tree and, in any tree, there are at least two vertices of degree one (the endpoints of the longest path in the tree), no matter the number of vertices.
• Statement S: There exists a bipartite graph with more than ten vertices which is 2-colorable.
  • This is true. If a graph is bipartite, it is 2-colorable. This means that the vertices can be colored using only two colors in such a way that no two adjacent vertices share the same color. Any graph with two or more vertices can be bipartite (split into two sets, where vertices in the same set are not adjacent), so a bipartite graph with more than ten vertices that is 2-colorable certainly exists.

Therefore, all the statements P, Q, R, and S are correct. The number of correct statements is 4.