Graph theory

The chromatic number of a triangle is ?

• 0
• 3
• 2
• 1

A connected non-trivial graph with no cut point is called

• block
• theta graph
• bridge
• none of the above

A graph is polyhedral iff it is planar and

• 2-connected
• 3-connected
• not connected
• acyclic

G is a plane (p, q) graph with r faces and k components then

• p+q+r= k+1
• p-q+r= k+1
• p-q+r= k+2
• p-q-r= k-1

In an Eulerian graph, Every vertex is of _______ degree

• odd
• even
• both a and b
• none of these

Every tree is a

• bipartite graph
• complete graph
• pseudo graph
• none of these

Let G be a connected planar graph with 10 vertices .if the number of edges in each face is 3 then the number of edges in G is?

• 18
• 22
• 24
• 83

Which algorithm can be used to find an eulerian cycle in a graph?

• Fleury’s algorithm
• Tarjan’s algorithm
• Kruskall's algorithm
• Prims algorithm

What is a path that visits every vertex exactly once called?

• Tree
• Eulerian path
• Hamiltonian path
• cycle

Identify the true statements (i) Every complete graph is Hamiltonian (i) Every wheel graph is Hamiltonian (iii) Every complete bipartite graph is Hamiltonian

• (i) only
• (i) and (ii) only
• (ii) only
• (iii) only