Graph Theory  Week 11 Assessment

Graph Theory 
Week 11 Assessment
1. Let 𝐺𝐺 and 𝐻𝐻 be graphs with incidence matrices
𝑀𝑀𝐺𝐺 =
⎣
⎢
⎢
⎢
⎡
1 1 1 1 0 0 0 0
1 0 0 0 1 1 1 0
0 1 0 0 1 0 0 1
0 0 1 0 0 1 0 1
0 0 0 1 0 0 1 0⎦
⎥
⎥
⎥
⎤
; 𝑀𝑀𝐻𝐻 =
⎣
⎢
⎢
⎢
⎡
1 1 1 1 0 0 0 0
1 0 0 0 1 1 1 0
0 1 0 0 1 0 0 1
0 0 1 0 0 1 0 0
0 0 0 1 0 0 1 1⎦
⎥
⎥
⎥
⎤
These matrices are the same except the last two entries in the final column are switched.
A. Draw 𝐺𝐺 and 𝐻𝐻
B. Determine, with justification, whether 𝐺𝐺 and 𝐻𝐻 are isomorphic graphs.
2. Given a simple graph 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸), we define its complement 𝐺𝐺 = �𝑉𝑉, 𝐸𝐸� as the simple graph
with the same vertex set and where two distinct vertices in 𝐺𝐺 are joined by an edge in 𝐺𝐺 if and
only if they are not joined by an edge in 𝐺𝐺. Here, the set 𝐸𝐸 is defined as
𝐸𝐸 = {𝑢𝑢𝑢𝑢: 𝑢𝑢 ∈ 𝑉𝑉, 𝑣𝑣 ∈ 𝑉𝑉, 𝑢𝑢 ≠ 𝑣𝑣 and 𝑢𝑢𝑢𝑢 ∉ 𝐸𝐸}.
A. Suppose 𝐺𝐺 is the six-cycle drawn below. Draw its complement 𝐺𝐺.
B. Suppose 𝐺𝐺 is an 𝑟𝑟-regular simple graph of order 𝑛𝑛. Explain why 𝐺𝐺 is an 𝑠𝑠-regular simple
graph of order 𝑛𝑛 and determine the value of 𝑠𝑠 in terms of 𝑟𝑟.
C. If 𝐺𝐺 = 𝐾𝐾𝑝𝑝,𝑞𝑞 where 𝑝𝑝 and 𝑞𝑞 are positive integers, describe 𝐺𝐺.
3. Consider the graph 𝐺𝐺 below
A. Write down an incidence matrix and an adjacency matrix for 𝐺𝐺.
B. Determine the radius and the diameter of 𝐺𝐺.
C. This is the graph from question 3 in homework 6. Explain why (𝑥𝑥 − 𝑘𝑘) is a factor of its
chromatic polynomial for every 𝑘𝑘 ∈ {0,1,2,3}. You are not required to find the chromatic
polynomial of 𝐺𝐺.
4. Recall that a circuit is a closed walk (one in which the starting and ending vertices are the same)
that does not repeat an edge. Explain why if 𝐺𝐺 has a nontrivial circuit, then it must have a
nontrivial cycle.
5. Let 𝑇𝑇 be a full ternary (3-ary) tree of height 7.
A. Determine, with justification, a tight upper bound on the number of vertices 𝑇𝑇 can have.
B. Determine, with justification, a tight upper bound on the number of edges 𝑇𝑇 can have.
C. Determine, with justification, a tight upper bound on the number of leaves 𝑇𝑇 can have.
D. Determine, with justification, whether it is possible for 𝑇𝑇 to have exactly 100 leaves.
6. For integers 𝑞𝑞 ≥ 1 and 𝑟𝑟 ≥ 3, the cylinder graph 𝑺𝑺𝒒𝒒,𝒓𝒓 is defined as 𝑆𝑆𝑞𝑞,𝑟𝑟 = 𝑃𝑃𝑞𝑞 × 𝐶𝐶𝑟𝑟. For instance,
𝑆𝑆5,3 is drawn below:
A. Determine, in terms of 𝑞𝑞 and 𝑟𝑟, the number of vertices in 𝑆𝑆𝑞𝑞,𝑟𝑟
B. Determine, in terms of 𝑞𝑞 and 𝑟𝑟, the number of edges in 𝑆𝑆𝑞𝑞,𝑟𝑟
C. Show that 𝑟𝑟 is even if and only if 𝑆𝑆𝑞𝑞,𝑟𝑟 is bipartite.
1
2
3
4
5
6
7