WorksheetsGraph theory
Total questions: 15
Worksheet time: 12mins
The father of Graph theory is the famous mathematician (a) .
Write about the proof of the four colour theorem.
Let G be a connected planar graph, and let n, m and f denote, respectively, the numbers of vertices, edges, and faces in a plane drawing of G. Then
n−m+f=2
n−m −f=2
n−m+f=4
n+m−f=2
Which of the following is true?
A graph may contain no edges and many vertices
A graph may contain many edges and no vertices
A graph may contain no edges and no vertices
A graph may contain no vertices and many edges
Which of the above graphs is/are NOT planar?
G1
G2
G3
G4
Which one shows subgraph?
(answer can be more than one)
Which Theorem is represented by the map presented?
Kruskal's Theorem
Four Color Theorem
Prim's Theorem
Coloring is fun!
Tina, Jessie, John, Bill, and Andy are all members of the social networking website Facebook. The site allows members to be “friends” with each other. It turns out that Bill and John are friends, as are Tina and Andy. Jessie is friends with everyone. Who is "E" ?
(a)
What is the degree of vertex 4?
3
4
5
7
The graph represents the following vocabulary term.
Cycle
Path
Complete Graph
Complete Bipartite Graph
Intuitively, graphs are isomorphic if they are basically the same, or better yet, if they are the same except for the names of the vertices.
True
False
Which vocabulary term describes the graph?
circuit
path
complete graph
polygon
Which two vertices are adjacent vertices?
5 is adjacent to 6
3 is adjacent to 6
4 is adjacent to 1
3 is adjacent to 2
Which of the following are isolated vertices?
F
G
D
F and G
The graph is an example of a
Path
Cycle
Complete Bipartite Graph
Complete Graph
