Graph Theory - Quiz App

Q1: In a simple graph with n vertices, what is the maximum number of edges if the graph is bipartite?

⌊n²/4⌋ ⌈n²/4⌉ n(n-1)/2 n(n-1)/4

Q2: Which of the following graphs is NOT planar?

K₄ K₃,₃ K₂,₃ K₅

Q3: What is the chromatic number of a complete graph Kₙ?

1 n n-1 ⌈n/2⌉

Q4: In a connected graph G, which of the following is TRUE about a cut-vertex?

A cut-vertex always belongs to every spanning tree A cut-vertex may or may not belong to a spanning tree A cut-vertex belongs to at least two biconnected components A cut-vertex has degree at least 2

Q5: What is the minimum number of edges in a connected graph with n vertices?

n-1 n n(n-1)/2 ⌈n/2⌉

Q6: Which of the following statements is TRUE about Hamiltonian graphs?

Every Hamiltonian graph is Eulerian Every Eulerian graph is Hamiltonian A Hamiltonian graph has a cycle containing all vertices A Hamiltonian graph has a cycle containing all edges

Q7: What is the degree sequence of a graph with 5 vertices if it is a regular graph?

All degrees are equal All degrees are distinct Degrees sum to 10 Degrees sum to 20

Q8: In a planar graph, which of the following is TRUE about the faces?

Every face is bounded by a cycle Every face has length at least 3 The number of faces is always even All faces have the same length

Q9: What is the maximum number of edges in a planar graph with n ≥ 3 vertices?

3n - 6 3n - 3 n(n-1)/2 2n - 4

Q10: Which of the following graphs is Eulerian?

A graph where every vertex has even degree A graph where every vertex has odd degree A graph with exactly two vertices of odd degree A graph with no cycles

Q11: In a tree with n vertices, how many edges does it have?

n-1 n n+1 2n-2

Q12: What is the Ramsey number R(3,3)?

4 5 6 7

Q13: Which of the following is TRUE about the adjacency matrix of a graph?

It is always symmetric for undirected graphs It is always skew-symmetric It is always diagonalizable It has all positive entries

Q14: In a bipartite graph, which of the following is TRUE?

All cycles have even length All cycles have odd length There are no cycles All vertices have even degree

Q15: What is the edge connectivity of a complete graph Kₙ?

n-1 n n-2 ⌈n/2⌉

Q16: Which of the following is TRUE about graph isomorphism?

Two graphs are isomorphic iff they have the same degree sequence Two graphs are isomorphic iff they have the same number of vertices and edges Graph isomorphism preserves adjacency and non-adjacency Graph isomorphism preserves only vertex degrees

Q17: In a graph, what is the relationship between the chromatic number and the clique number?

χ(G) ≤ ω(G) χ(G) ≥ ω(G) χ(G) = ω(G) χ(G) = ω(G) + 1