Graph Theory  Assignment 4

Graph Theory 
Assignment 4
1. Let 𝐺 be a graph without loops.
We discussed the incidence matrix 𝑀 that has 𝑛 rows (a row for each vertex) and 𝑚 columns (a
column for each edge).
Recall that the entry 𝑀𝑖𝑗 has the formula
𝑀𝑖𝑗 = {
1 if vertex 𝑖 is an endpoint of edge 𝑗
0 otherwise
Now consider the matrix 𝑀𝑀𝑇
. The results of parts A and B below let us write 𝑀𝑀𝑇 = 𝐷 + 𝐴
where 𝐷 is the diagonal matrix containing the degrees of the vertices and 𝐴 is the adjacency matrix
that encodes the numbers of edges joining pairs of vertices.
A. Explain why (𝑀𝑀𝑇
)𝑖𝑖, the diagonal entry in position 𝑖, is the degree of vertex 𝑖.
B. Explain why for 𝑖 ≠ 𝑗, the entry (𝑀𝑀𝑇
)𝑖𝑗 is the number of edges joining vertex 𝑖 to vertex 𝑗.
C. Determine the matrices 𝑀, 𝑀𝑀𝑇
,𝐷 and 𝐴 for the graph drawn below (the vertices are labeled
1,2,3,4,5 and the edges are labeled 14,15,24,25,34,35 denoting the corresponding endpoints).
1 2
3
4 5
14
15
24 34
25 35
2. We let 𝐺 = (𝑉, 𝐸) be a connected graph. For any vertex 𝑣 ∈ 𝑉, define its eccentricity by the
formula
ecc(𝑣) = max{𝑑(𝑢, 𝑣): 𝑢 ∈ 𝑉}
where 𝑑(𝑢, 𝑣) is the distance between 𝑢 and 𝑣.
A. Let 𝐺 be the graph drawn below. Label each vertex with its eccentricity. This has already been
done for 𝑣10; here, 𝑑(𝑣5, 𝑣10) = 𝑑(𝑣6, 𝑣10) = 𝑑(𝑣13, 𝑣10) = 3 and no vertex is further from
𝑣10.
B. The diameter of a graph is the maximum among the eccentricities of its vertices and the radius
of a graph is the minimum among the eccentricities of its vertices. What is the diameter and
radius of the graph in part A?
A central vertex is a vertex 𝑣 such that ecc(𝑣) = radius(𝐺). Which of the vertices in the graph
in part A are central vertices?
C. A peripheral vertex is a vertex 𝑣 such that ecc(𝑣) = diameter(𝐺). Which of the vertices in the
graph in part 𝐴 are peripheral vertices?
Let 𝑢 and 𝑣 be vertices such that 𝑑(𝑢, 𝑣) = diameter(𝐺). Explain why 𝑢 and 𝑣 must be
peripheral vertices.
D. Suppose 𝑣𝑖 and 𝑣𝑗 are adjacent vertices. Explain why ecc(𝑣𝑖
) and ecc(𝑣𝑗) differ by at most 1.
E. Explain why for any connected graph 𝐻, radius(𝐻) ≤ diameter(𝐻).
F. Let 𝑤 be a central vertex for the graph 𝐻 in part G. Use the fact that 𝑑(𝑢, 𝑣) ≤ 𝑑(𝑢, 𝑤) +
𝑑(𝑤, 𝑣) for any vertices 𝑢 and 𝑣 to explain why diameter(𝐻) ≤ 2 radius(𝐻).
3
3. Let 𝐺 be a graph without loops and 𝑟 be a vertex of 𝐺; we will call 𝑟 the “root” vertex. We will say
that 𝑢 ≈ 𝑤 if 𝑑(𝑟, 𝑢) = 𝑑(𝑟, 𝑤). This means 𝑢 and 𝑤 are the same distance from 𝑟.
A. Show that the relation ≈ is reflexive.
B. Show that the relation ≈ is symmetric.
C. Show that the relation ≈ is transitive.
D. Describe [𝑟], the equivalence class of 𝑟 under ≈.
E. If 𝑟𝑢 is an edge, briefly describe [𝑢], the equivalence class of 𝑢 under ≈.