CS453 - Graph Theory  - Assignment 4 - Solved

1.     Recall that the adjacency matrix of a simple graph 𝐺 with vertex set 

{𝑣1, 𝑣2, … , 𝑣𝑛} is the 𝑛 × 𝑛 matrix 𝐴 with entries 

                                                                  𝐴𝑖,𝑗 = {1      𝑣𝑖 is adjacent to 𝑣𝑗 

                                                                                     0             otherwise

A.    Let 𝐾3,4 be the complete bipartite graph with vertices 

{𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5,𝑣6, 𝑣7} and where vertices 𝑣𝑖 and 𝑣𝑗 are adjacent if and only if 𝑖 and 𝑗 have different parity (one of 𝑖 or 𝑗 is odd and the other is even.)  What does the adjacency matrix 𝐴 look like in this case? 

B.     Let 𝐾3,4 be the complete bipartite graph with vertices 

{𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5,𝑣6, 𝑣7} and where vertices 𝑣𝑖 and 𝑣𝑗 are adjacent if and only if (𝑖 ≤ 3 and 𝑗 ≥ 4) or  (𝑖 ≥ 4 and 𝑗 ≤ 3).  What does the adjacency matrix 𝐴 look like in this case? 

 

 

             

2.     We let 𝐺 be a connected graph.  For any vertex 𝑣   𝑉, define its eccentricity by the formula ecc . 

This is the length of “longest among all shortest paths with 𝑣 as an endpoint.” 

a.     Let 𝐺 be the graph drawn below.  Label each vertex with its eccentricity. 

 

 

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.  For the graph 𝐺 drawn in part a, what is its diameter and radius? 

c.     A central vertex is a vertex 𝑣 such that ecc(𝑣) = radius(𝐺).  Which of the vertices in the graph 𝐺 are central vertices? 

d.    A peripheral vertex is a vertex 𝑣 such that ecc(𝑣) = diameter(𝐺).  Which of the vertices in graph 𝐺 are peripheral vertices? 

e.     Explain why it is important for these definitions that 𝐺 be a connected graph. 

f.       Show that for any connected graph 𝐻,  radius  diameter  radius(𝐻). 

One inequality is quite easy and the second can be handled using a central vertex and the triangle inequality. 

  

           

3.     Recall that a bridge is an edge whose deletion increases the number of components of a graph.  Also, a link is another term for “non-bridge.” 

 

a.     In the graph 𝐺 (same as in problem 2a) below, which edges are bridges and which edges are links? 

 

 

b.    If you delete all of the bridges, how many components remain? 

c.     Suppose, instead, you deleted links one at a time until the remaining graph had no links.  How many links could you delete in this process? 

 

4.     Let 𝐺 be a graph and 𝑥 be a vertex of 𝐺.  We say that 𝑢~𝑤 if 𝐷(𝑢, 𝑥) = 𝐷(𝑤, 𝑥).  When we discuss trees, the equivalence classes will be the levels of a tree. 

a.     Show that this relation is reflexive. 

b.    Show that this relation is symmetric. 

c.     Show that this relation is transitive. 

d.    Suppose 𝑥 has no loops and suppose 𝑢𝑥 is an edge.  Briefly describe the equivalence class [𝑢].