Determine the number of connected components in the subgraph induced by each of following subsets of vertices

⦁ Below is a map (represented as a graph) of the islands (vertices) and safe naval passageways (edges).

Determine the number of connected components in the subgraph induced by each of following subsets of vertices. No justification is necessary.
(a) {a, b, c, d, e}
(b) {f, g, h, i, j}
(c) {a, b, e, h, i}
(d) {c, f, g, i, j}
(e) {a, c, d, g, j}

Get Your Custom Essay Written From Scratch
Are You Overwhelmed With Writing Assignments?
Give yourself a break and turn to our top writers. They’ll follow all the requirements to compose a premium-quality piece for you.
Order Now

⦁ In the post-medieval Mavala, there are n islands, some of which are connected by
naval routes. In fact, the islands and naval routes form a tree. Among the Mavala islands,
historians have mostly researched the so-called Oval island, referred to as u. It has been concluded that the Oval had d naval routes incident to it. Prove that the tree formed by the islands and naval routes of Mavala has at least d islands that are each connected to only one naval route. Hint: Consider the induced subgraph with vertex set V \ {u}.

⦁ You are at a carnival over the summer. At one of the games, there is a board containing a set
V of houses and a set E of paths connecting the houses. You realize that you can reach any
other house by following a sequence of paths regardless of which house you start at. You also
notice that |E| = |V | − 1. Prove that the graph formed by the board is a tree.

⦁ Cindy begins to construct her own graph G with tents as vertices and pathways as edges. Suddenly, she notices that G is both connected and has exactly one spanning tree. Find the next best thing (a theoretical tree!) by proving that the graph G is itself a tree.

⦁ Brandon decides to host a giant competition between members of the clan. For each pair of clan members that plays between each other, he adds an undirected edge between them (not every pair has to play each other). He notices that the resulting network of members and edges is connected and contains at least one cycle. He also decides to partition the members of his clan into two groups in order to train everyone for the next Clan War. However, he partition the members in such a way that no two members in the same group have an edge between them. In other words, if two members are neighbors in the network, they must be in opposite groups. Prove that Brandon can remove some of the edges of the network so that it remains connected and Brandon can make the partition he desires.

⦁ Ethan has a plan to meet with m investors and n distributors all across Silicon Valley. Ethan always wants to alternate the two types of meetings. That is, after he meets with an investor, he will meet with one of the n distributors, but not another investor, and vice versa. Note that he can start by meeting with either an investor or a distributor and once finishing a meeting, he can choose to attend any meeting of the other type.
Note that the meetings and the paths between them form a complete bipartite graph
where m, n ≥ 1, has m red nodes, n blue nodes and has an edge between every red and every
blue node. There are no edges between nodes of the same color. For illustration, here is K3,2:

(a) Let D be the number of edges of that we have to delete from the graph to obtain a
spanning tree. Prove that D is divisible by m − 1.
(b) Assume that m > n. Prove that the length of a longest path in is even.

⦁ The kingdoms that Ryan protects can be modelled as an acyclic graph G with 100 leaves and no isolated nodes, where each kingdom is represented by a connected component. Ryan does know two things about the kingdoms he protects: he protects less than 50 kingdoms and there is a castle, represented in G by a vertex, that is connected to at least three other castles by paths, represented in G by edges. Ryan ventures to make a claim: the set of kingdoms that a knight protects is less than 50 if and only if there is a castle connected to at least three others by paths. In other words, G has < 50 connected components if and only if it has at least one vertex of degree 3 or more. Prove this statement.

⦁ In 1510, in the medieval Polynesia of Mavala, there exist n ≥ 4 islands. The routes connect the islands in such a way that the Polynesia actually makes up a path graph (routes are edges, islands are vertices). In 1610, the configuration of naval routes in the Mavala Polynesia has changed. In fact, any two islands that were initially connected by a direct naval route, no longer have this route connecting them. Further, any two islands not initially connected by a direct route now share one. Prove that in 1610, the length of a longest path of naval routes (of the form where all routes are distinct) is n − 1.

⦁ Austin was the valedictorian of his class in high school. However, his high school class only
contained four people. Furthermore, his high school had a strange ranking system where instead of having class rank, they represented their GPA hierarchy as a rooted tree (T, a), where T = (V, E) is an undirected tree and a is the root node (Austin). In order to derive feasible class ranks to comply with district policy, his class looked at the rooted tree as a digraph, which becomes a DAG with the root (Austin) as the only source. Then, they perform several topological sorts to find all valid class rankings. Below are all possible topological sorts of the DAG representing Austin’s class with students Becky, Clara, and Derek:

Reconstruct the rooted tree using these topological sorts. List all edges in E for our rooted tree. Justify your answer.

⦁ Petros is bored and decides to draw a bunch of ovals, squares, triangles, and hexagons. He
draws n shapes in total. He then adds a bunch of directed edges between these shapes, such
that the resulting picture has no directed cycles, all ovals have in-degree of 0, and all squares
have out-degree of 0.
(a) How many strongly connected components are there in the picture? Justify your answer.
(b) Petros decides to add a directed edge from square to every oval in the picture. Let G′ be
the resulting picture. How many strongly connected components are there in G′? Justify your answer.

⦁ Magill has created a map of the n ≥ 2 possible locations to park scooters near campus, as well as the bidirectional paths that connect these parking spots. The map includes a theater and a library as special parking locations that are designated for scooter pick-up. Magill wants to assign a one-way direction to each scooter path on the map such that: all paths connected to theater lead away from theater, all paths connected to library lead to the stadium, and for any other parking spot, it is impossible to return to that same spot once you’ve left it. Prove that it is possible to satisfy these conditions.