Suppose new a friend tells you about their favourite simple, connected, undirected graph that has 7 vertices and 29 edges. Which of the following is true?
A simple, connected, undirected graph contains 66 edges.
The least upper bound for the number of vertices is:
Least upper bound
The greatest lower bound for the number of vertices is:
Greatest lower bound
(Note that each of the bounds should be a feasible number of vertices.)
Could the graph be complete?
Suppose a simple connected undirected graph has vertices whose degrees are given in the following table:
| Vertex | Degree |
|---|---|
| 0 | 4 |
| 1 | 4 |
| 2 | 3 |
| 3 | 1 |
| 4 | 1 |
| 5 | 1 |
| 6 | 1 |
| 7 | 1 |
| 8 | 1 |
| 9 | 1 |
The graph is sparse so it should not be represented with an adjacency matrix, additionally, it's not complete as there are too few edges, there are also not enough edges to form a cycle as the graph is connected, meaning we only have option a.
What can be said about the graph?
Suppose a simple connected undirected graph has vertices whose degrees are given in the following table:
| Vertex | Degree |
|---|---|
| 0 | 4 |
| 1 | 4 |
| 2 | 3 |
| 3 | 3 |
| 4 | 1 |
| 5 | 1 |
| 6 | 1 |
| 7 | 1 |
| 8 | 1 |
| 9 | 1 |
What can be said about the graph?
Suppose a simple connected undirected graph has vertices whose degrees are given in the following table:
| Vertex | Degree |
|---|---|
| 0 | 5 |
| 1 | 4 |
| 2 | 3 |
| 3 | 1 |
| 4 | 1 |
| 5 | 1 |
| 6 | 1 |
| 7 | 1 |
| 8 | 1 |
| 9 | 1 |
What can be said about the graph?
Suppose a simple connected undirected graph has vertices whose degrees are given in the following table:
| Vertex | Degree |
|---|---|
| 0 | 3 |
| 1 | 3 |
| 2 | 3 |
| 3 | 1 |
| 4 | 1 |
| 5 | 1 |
| 6 | 1 |
| 7 | 1 |
| 8 | 1 |
| 9 | 1 |
What can be said about the graph?
Suppose we run depth first search on a connected, undirected graph with n vertices and
For a simple connected graph with
For a simple connected graph G with 51 vertices, which of the following options cannot be the number of edges of G?
Suppose G is fully connected (every vertex has an edge to every other vertex). What is the runtime of adding a vertex to the graph such that the graph remains fully connected. Assume that the graph is represented using an adjacency list and has n vertices and m edges. (Assume constant time when inserting to list)
For a simple connected graph with 45 vertices, which of the following options cannot be the number of edges of G?
One version of DFS proceeds as: (1) Push the root with no associated edge. (2) While the stack is not empty, pop the next node and its associated edge (if any); if it has been marked as visited, skip it; otherwise, mark it as visited, mark its attached edge (if any) as a tree edge, and for each node adjacent to it, push the adjacent node along with the edge connecting to it from the current node.
Now, consider two vertices x and y that were simultaneously on the stack at some point during execution of DFS from vertex s in an undirected graph. Which of the following is/are true when DFS completes?
I. The number of edges on the shortest path from s to x is at most one more than the number of edges on the shortest path from s to y.
II. The difference in the number of discovery (tree) edges on the path from s to x and from s to y is at least 1.
III. There is a path from x to y.
Suppose G is fully connected (every vertex has an edge to every other vertex). What is the runtime of adding a vertex to the graph such that the graph remains fully connected. Assume that the graph is represented using an adjacency matrix and has n vertices and m edges.(Assume no resizing needed)