Graph theory questions from my Algorithms quiz today that I'd like help understanding

Question

Today I had my algorithms quiz for the semester and I can't figure out these two questions and they've been bugging me all day. I've gone through my notes and the lecture notes and I'm still unsure. I would appreciate it if someone could take a look and provide some insight into these questions. These are not homework and I've already sat the quiz.

True or False questions

1) [Paraphrased] The maximum number of edges in a bipartite graph with n vertices is n(n-1)/2.

I put this down as False, my logic is that n verticies means we have two n/2 rows. The first node has n/2 connections to the second row, the second row has n/2 connections to the second row... etc...

Hence, I calculated the maximum number of edges in a bipartite graph with n vertices to be (n^2/4).

2) [Paraphrased] Is it possible to take a cut, that is not necessarily the minimum s-t cut in a graph with directed flows (Ford–Fulkerson algorithm) such that the flow capacity is greater than the s-t cut capacity?

I put down false, but I don't understand the question... Is it possible to take an s-t cut such that the flow capacity is greater? I know the weak duality theorem and 'max flow = min cut' so I put down false, but I have no idea.

Short answer question:

1) Explain an efficient way to test weather a graph is connected.

I suggested doing a breadth first search and if there were nodes that were not found by the BFS algorithm in the graph, then it was not connected. I wrote down the running time was O(m+n) hence it was an efficient algorithm to use. It was worth two marks and it was the final question but I'm now worried it was a trick question.

2) In the graph:

List the sets of vertices which demonstrate minimum vertex cover [paraphrased]

My answer was {A, D}, {A, E}, {B, C}, {B, D}, {C, E}, but now I'm worried it was just {A}, {B}, {C}, {D}, {E}...

Thanks for taking the time to read! :)

Answer 1

I only have the answer to the first graph right now, but you are correct.

In a bipartite graph, there have to be two sets of nodes - say x in the first group and (n - x) in the second.

The maximum number of edges in this graph will then be x(n-x), or nx - x^2.

The maximum value of nx - x^2 is x = (n/2)

So the maximum number of edges in the graph is (n/2) * (n - (n/2)) = (n^2)/4, as you pointed out.

Answer 2

Graph Connectivity:

You are right about using BFS. After one iteration of BFS, if all the nodes are visited then we can conclude that the graph is connected.

Alternatively, this can be also done using DFS. Approach remains the same.

Answer 3

1) has been answered, and I agree that you were right.

2): The question seems ambiguous as stated.

such that the flow capacity is greater than the s-t cut capacity

the flow capacity of what? of the whole network? or of the cut?

If the latter, it seems to be asking can A > A, which is obviously false. If the former, again it's clear that the answer is false. If it were possible to find such a cut, then max-flow=min-cut would not be true: the max flow of the network would be greater than the minimum capacity of an s-t cut.

However it is possible to take a cut such that the flow capacity of the cut is greater than the minimum s-t cut capacity of the network. You don't suppose that's what they meant? For example, in the example at the top of this article, if you cut between s and the rest of the network, the capacity of the cut is greater than the minimum s-t cut capacity of the network.

But even that interpretation seems unlikely because it's pretty trivial... the implication of a "minimum" is that there may be greater values.

Maybe it would help to see the exact original wording.

Short answer:

1) has been answered, although I don't understand what m is (in O(m+n)), unless you're talking about a bipartite graph?

2) I agree with @glebm that you got it wrong... sorry. "Vertex cover of a graph is a set of vertices", but you seem to have written a list of edges? followed by a list of singleton sets of vertices?

Vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.

Since this is a complete graph, all vertices are interchangeable. So we don't really care which vertices, but only how many vertices we need in order to touch all the edges. The answer is not hard to find. If we pick any three vertices, the edge connecting the other two vertices is not "covered". QED.

In fact we can prove that for any complete graph of n vertices, the minimum vertex cover requires n-1 vertices.