Virtual Labs

Planarity of Graphs

Which of the following best describes why K₅ (complete graph with 5 vertices) is non-planar?

a: It has too many vertices Explanation

Explanation

b: It has 10 edges, which is too many for any planar graph Explanation

Explanation

c: It cannot be drawn on a flat surface without edge crossings Explanation

Explanation

d: It violates Euler's formula Explanation

Explanation

What is the minimum number of faces in any connected planar graph?

a: 1 face Explanation

Explanation

b: 2 faces Explanation

Explanation

c: 3 faces Explanation

Explanation

d: It depends on the number of vertices Explanation

Explanation

In the context of planar graphs, what does a 'subdivision' of a graph mean?

a: Dividing the graph into smaller disconnected components Explanation

Explanation

b: Adding new vertices along existing edges Explanation

Explanation

c: Removing vertices from the graph Explanation

Explanation

d: Creating multiple copies of the same graph Explanation

Explanation

A connected planar graph has 8 vertices and 12 edges. Using Euler's formula, how many faces does it have, and is this configuration possible?

a: 6 faces, and this is possible Explanation

Explanation

b: 6 faces, but this is impossible for a planar graph Explanation

Explanation

c: 4 faces, and this is possible Explanation

Explanation

d: 8 faces, but this violates planarity constraints Explanation

Explanation

Which statement about the cube graph (representing a 3D cube's vertices and edges) is correct?

a: It is non-planar because it represents a 3D object Explanation

Explanation

b: It is planar and can be drawn as a square with internal connections Explanation

Explanation

c: It has 8 vertices, 12 edges, and violates Euler's formula Explanation

Explanation

d: It is non-planar because it contains a subdivision of K₅ Explanation

Explanation

For a simple connected planar graph (no multiple edges or self-loops), what is the relationship between edges and vertices?

a: E ≤ V + 4 Explanation

Explanation

b: E ≤ 2V - 4 Explanation

Explanation

c: E ≤ 3V - 6 Explanation

Explanation

d: E = V - 1 Explanation

Explanation

Consider a planar graph where every face (including the outer face) is bounded by exactly 4 edges, and every vertex has degree 3. If the graph has F faces, derive the relationship between vertices V and faces F.

a: V = 2F Explanation

Explanation

b: V = F + 2 Explanation

Explanation

c: V = 4F/3 Explanation

Explanation

d: V = 3F/2 Explanation

Explanation

Using Kuratowski's theorem, which of the following graphs is definitely non-planar?

a: A graph that contains K₄ as a subgraph Explanation

Explanation

b: A graph that contains a cycle of length 5 with all diagonals added Explanation

Explanation

c: A graph with 6 vertices where each vertex connects to exactly 4 others Explanation

Explanation

d: The Petersen graph (which contains K₃,₃ as a subdivision) Explanation

Explanation

In a maximal planar graph with n vertices (n ≥ 3), every face is a triangle. If such a graph has exactly 20 triangular faces, how many vertices does it have?

a: 10 vertices Explanation

Explanation

b: 12 vertices Explanation

Explanation

c: 14 vertices Explanation

Explanation

d: 22 vertices Explanation

Explanation