, MAT3707/102/0/2022
Tutorial letter 102/0/2022
DISCRETE MATHEMATICS:
COMBINATORICS
MAT3707
Year module
Department of Mathematical Sciences
IMPORTANT INFORMATION:
This tutorial letter contains questions for assignment 01.
BARCODE
university
Define tomorrow. of south africa
, MAT3707
ASSIGNMENT 01
UNITS 1, 2 in the Study Guide
DUE DATE: 29 APRIL 2022
QUESTION 1
Draw two non-isomorphic graphs with degree sequence 3,3,2,1,1,1,1. Explain why your two graphs are
non-isomorphic. [4]
QUESTION 2
A graph is said to be r − regular if every vertex has degree r.
(a) Find out whether the complement of a regular graph is regular.
(b) Find, up to isomorphism, all 4−regular graphs of order 7.
(Instead of trying to find 4−regular graphs on 7 vertices, first find complements of 4−regular
graphs on 7 vertices.) [3+6=9]
QUESTION 3
(a) Prove that if G = (V1 ∪ V2 , E) is a bipartite graph, then
X X
|E| = deg(v) = deg(v)
v∈V1 v∈V2
(b) Use part (a) to prove that if a graph has odd order and is regular of degree r ≥ 1, then it is not
bipartite.
[4+4=8]
QUESTION 4
n(n − 1)
(a) Prove that a complete graph with n vertices has edges.
2
(b) A graph is self-complementary it is isomorphic to its complement.
(i) Prove that there is no self-complementary graphs of order 3.
(ii) Give an example of a self-complementary simple graph with 4 and 5 vertices respectively.
[4+3+4=11]
2
, MAT3707/102/0/2022
QUESTION 5
Determine which pairs of graphs below are isomorphic? EXPLAIN FULLY.
[12]
QUESTION 6
If a connected planar graph with n vertices, all of degree 4, has 10 regions, determine n. [5]
QUESTION 7
Consider a connected planar graph with v(≥ 3) vertices, e edges and r regions.
Show that if e = 3v − 6 then each region is a triangle. [6]
QUESTION 8
(a) Show that the Petersen graph contains a subgraph that is a K3,3 configuration.
(b) Does it contain a subgraph that is a K5 configuration?
(c) Deduce that the Petersen graph is non-planar.
[3 + 2 + 2 = 7]
QUESTION 9
Prove that if a connected graph G has 11 vertices, then either G or its complement G must be
nonplanar.
3
Tutorial letter 102/0/2022
DISCRETE MATHEMATICS:
COMBINATORICS
MAT3707
Year module
Department of Mathematical Sciences
IMPORTANT INFORMATION:
This tutorial letter contains questions for assignment 01.
BARCODE
university
Define tomorrow. of south africa
, MAT3707
ASSIGNMENT 01
UNITS 1, 2 in the Study Guide
DUE DATE: 29 APRIL 2022
QUESTION 1
Draw two non-isomorphic graphs with degree sequence 3,3,2,1,1,1,1. Explain why your two graphs are
non-isomorphic. [4]
QUESTION 2
A graph is said to be r − regular if every vertex has degree r.
(a) Find out whether the complement of a regular graph is regular.
(b) Find, up to isomorphism, all 4−regular graphs of order 7.
(Instead of trying to find 4−regular graphs on 7 vertices, first find complements of 4−regular
graphs on 7 vertices.) [3+6=9]
QUESTION 3
(a) Prove that if G = (V1 ∪ V2 , E) is a bipartite graph, then
X X
|E| = deg(v) = deg(v)
v∈V1 v∈V2
(b) Use part (a) to prove that if a graph has odd order and is regular of degree r ≥ 1, then it is not
bipartite.
[4+4=8]
QUESTION 4
n(n − 1)
(a) Prove that a complete graph with n vertices has edges.
2
(b) A graph is self-complementary it is isomorphic to its complement.
(i) Prove that there is no self-complementary graphs of order 3.
(ii) Give an example of a self-complementary simple graph with 4 and 5 vertices respectively.
[4+3+4=11]
2
, MAT3707/102/0/2022
QUESTION 5
Determine which pairs of graphs below are isomorphic? EXPLAIN FULLY.
[12]
QUESTION 6
If a connected planar graph with n vertices, all of degree 4, has 10 regions, determine n. [5]
QUESTION 7
Consider a connected planar graph with v(≥ 3) vertices, e edges and r regions.
Show that if e = 3v − 6 then each region is a triangle. [6]
QUESTION 8
(a) Show that the Petersen graph contains a subgraph that is a K3,3 configuration.
(b) Does it contain a subgraph that is a K5 configuration?
(c) Deduce that the Petersen graph is non-planar.
[3 + 2 + 2 = 7]
QUESTION 9
Prove that if a connected graph G has 11 vertices, then either G or its complement G must be
nonplanar.
3
