Crossings in a particular drawing do not establish nonplanarity. K₄ embeds as an outer triangle with the fourth vertex inside. Q₃ embeds as two nested squares with corresponding corners connected. Both have crossing-free embeddings, B.
More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions
GATE 2010 CS (CS1) Q11– For graph G=(V,E), let (G)= di dd, where i d counts vertices of degree d. If different…
GATE 2010 CS (CS1) Q38– Which sequences cannot be degree sequences of simple graphs? I: 7,6,5,4,4,3,2,1 II:…
GATE 2015 CS (CS2) Q61– A self-complementary graph is isomorphic to its complement. What must its vertex count n…
GATE 2015 CS (CS2) Q62– A bridge is an edge whose removal disconnects a connected graph. Which is true?
GATE 2026 CS (CS1) Q55– An undirected, unweighted, simple graph G(V, E) is said to be 2-colorable if there exists…
GATE 2026 CS (CS2) Q36– Consider a complete graph K n with n>4 vertices. Each spanning tree of K n is represented…
