Search Header Logo
  1. Resource Library
  2. Math
  3. Data And Graphing
  4. Graph Theory
  5. Graph Theory Concepts And Properties
Graph Theory Concepts and Properties

Graph Theory Concepts and Properties

Assessment

Interactive Video

Mathematics

9th - 10th Grade

Hard

Created by

Thomas White

FREE Resource

The video demonstrates that the complete graph K5 and the complete bipartite graph K3,3 are non-planar. It uses edge bounds to prove the non-planarity of K5 and introduces a lemma for planar graphs without triangles to prove the non-planarity of K3,3. The video concludes by hinting at Kuratowski's theorem, which identifies forbidden subgraphs for planar graphs.

Read more

9 questions

Show all answers

1.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

What is the main objective of the video?

To prove that K5 and K3,3 are planar

To introduce Euler's formula

To prove that K5 and K3,3 are not planar

To discuss the properties of bipartite graphs

2.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

What is the edge bound for a maximal planar graph with n vertices?

3n - 6

4n - 8

2n - 4

n^2 - n

3.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

How many edges does the complete graph K5 have?

10

5

15

20

4.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

What is the condition for a graph to be planar according to the edge bound?

The number of edges must be less than or equal to 2n - 4

The number of edges must be exactly 3n - 6

The number of edges must be greater than 3n - 6

The number of edges must be less than or equal to 3n - 6

5.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

What additional condition is considered for the new edge bound?

The graph must have even cycles

The graph must be complete

The graph must have no triangles

The graph must be bipartite

6.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

What is the new edge bound for a planar graph with no triangles?

3n - 6

2n - 4

4n - 8

n^2 - n

7.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

How many vertices and edges does K3,3 have?

5 vertices and 9 edges

6 vertices and 12 edges

5 vertices and 10 edges

6 vertices and 9 edges

Access all questions and much more by creating a free account

Create resources

Host any resource

Get auto-graded reports

Google

Continue with Google

Email

Continue with Email

Classlink

Continue with Classlink

Clever

Continue with Clever

or continue with

Microsoft

Microsoft

Apple

Apple

Others

Others

Already have an account?