Compute the closeness centralities and betweenness centralities of each vertex on a graph with five vertices and four edges, arranged in a path.
Suppose that \(T\) is an arbitrary undirected tree, and choose arbitrarily a node of \(T\) to be its root.
Direct each edge in \(T\) from its child endpoint (the vertex farther from the root) to its parent vertex (the vertex closer to the root), and find a topological ordering of the resulting directed acyclic graph. What can you say about the number of neighbors of each vertex that are later than it in this ordering?
Direct each edge in the opposite direction, from parent to child, and find a topological ordering of the resulting directed acyclic graph. What can you say about the number of neighbors of each vertex that are later than it in this ordering? (Hint: compare it to the degree of the vertex. The answer will depend on whether the vertex is the root or not.)
The Moon–Moser theorem provides a construction of a graph with many independent sets (\(3^{n/3}\) of them), but it may seem a bit like cheating because the graph is very far from being connected. Find a connected graph with \(n\) vertices that has nearly as many independent sets.
Find a tree, and a vertex ordering on your tree, such that greedy coloring in this order uses four colors.