Virtual Labs

Planarity of Graphs

What is a planar graph?

a: A graph that can be drawn on a flat surface with no edge crossings Explanation

Explanation

b: A graph that has exactly 4 vertices Explanation

Explanation

c: A graph where all vertices are connected to each other Explanation

Explanation

d: A graph that represents a geometric plane Explanation

Explanation

Which of the following graphs is guaranteed to be planar?

a: K₅ (complete graph with 5 vertices) Explanation

Explanation

b: K₃,₃ (complete bipartite graph with 3+3 vertices) Explanation

Explanation

c: K₄ (complete graph with 4 vertices) Explanation

Explanation

d: Any graph with more than 10 edges Explanation

Explanation

In graph theory, what do we call the regions created when a planar graph is drawn?

a: Vertices Explanation

Explanation

b: Edges Explanation

Explanation

c: Faces Explanation

Explanation

d: Loops Explanation

Explanation

According to Euler's formula for connected planar graphs, if a graph has 6 vertices and 9 edges, how many faces does it have?

a: 3 faces Explanation

Explanation

b: 4 faces Explanation

Explanation

c: 5 faces Explanation

Explanation

d: 6 faces Explanation

Explanation

Which statement best describes Kuratowski's theorem?

a: A graph is planar if it has fewer than 5 vertices Explanation

Explanation

b: A graph is non-planar if it contains a subdivision of K₅ or K₃,₃ Explanation

Explanation

c: All complete graphs are non-planar Explanation

Explanation

d: Planar graphs must satisfy V + E = F Explanation

Explanation

A tree (connected graph with no cycles) with 8 vertices is always planar. How many edges does this tree have?

a: 6 edges Explanation

Explanation

b: 7 edges Explanation

Explanation

c: 8 edges Explanation

Explanation

d: 9 edges Explanation

Explanation

Consider a connected planar graph with 10 vertices where each vertex has degree 3 (connected to exactly 3 other vertices). Using Euler's formula and the handshaking lemma, determine if such a graph can exist.

a: Yes, it can exist and would have 8 faces Explanation

Explanation

b: Yes, it can exist and would have 7 faces Explanation

Explanation

c: No, it cannot exist because it violates Euler's formula Explanation

Explanation

d: No, it cannot exist because the degree sequence is impossible Explanation

Explanation

Which of the following is a correct application of planarity in real-world scenarios?

a: Circuit board design where wire crossings must be minimized to avoid short circuits Explanation

Explanation

b: Social network analysis where friendships are represented as planar graphs Explanation

Explanation

c: GPS navigation systems that only work with planar road networks Explanation

Explanation

d: Database design where planar graphs ensure faster query processing Explanation

Explanation

A maximal planar graph with n vertices (where n ≥ 3) has exactly 3n - 6 edges. If you have a maximal planar graph with 12 vertices, and you remove one edge, what is the maximum number of edges the resulting graph can have while remaining planar?

a: 29 edges Explanation

Explanation

b: 30 edges Explanation

Explanation

c: 31 edges Explanation

Explanation

d: 35 edges Explanation

Explanation