Understanding Planar Graphs

What is a planar graph?

• A graph that can only be drawn in three dimensions.

• A graph that contains no vertices.

• A graph where all edges must intersect.

• A graph that can be drawn on a plane without edges crossing.

Which of the following graphs is planar: K5, K3,3, or a triangle?

• square

• K3,3

• triangle

• K5

Can a graph with 5 vertices and 10 edges be planar?

• It depends on the graph structure

• No

• Yes

• Yes, if it has no cycles

What is the maximum number of edges in a planar graph with n vertices?

• 4n - 8

• 2n - 4

• 3n - 6

• n^2 - n

Is every tree a planar graph? Why or why not?

• Only some trees are planar graphs depending on their structure.

• No, trees can have crossings that make them non-planar.

• Yes, every tree is a planar graph.

• Trees are always non-planar due to their branching nature.

How can you determine if a graph is non-planar?

• A graph is non-planar if it contains a subgraph that is a subdivision of K5 or K3,3.

• A graph is non-planar if it contains a cycle of length 4.

• A graph is non-planar if it has more than 10 vertices.

• A graph is non-planar if it is colored with more than 3 colors.

What is Kuratowski's theorem in relation to planar graphs?

• A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 or K3,3.

• A finite graph is planar if it has no cycles.

• A finite graph is planar if and only if it contains a subgraph that is a subdivision of K3,3.

• A finite graph is planar if it contains a subgraph that is a subdivision of K5.

Can a planar graph have a face with more than 4 edges?

• No, a planar graph can only have faces with 3 edges.

• Yes, a planar graph can have a face with more than 4 edges.

• Yes, but only if it is a non-planar graph.

• No, all faces in a planar graph must have exactly 4 edges.

What is the significance of Euler's formula in planar graphs?

• Euler's formula establishes a relationship between the number of vertices, edges, and faces in planar graphs.

• Euler's formula is only applicable to non-planar graphs.

• Euler's formula is used to determine the colorability of graphs.

• Euler's formula calculates the area of a planar graph.

Provide an example of a planar graph and explain why it is planar.

• A complete graph with 5 vertices (K5) is a planar graph.

• A square (4 vertices, 4 edges) is a planar graph.

• A triangle (3 vertices, 3 edges) is a planar graph.

• A cycle graph with 6 vertices (C6) is a planar graph.