## graph theory proof or disproving

I was requested to prove or disprove the following statement if a graph is conncted does it necessarily means that E>(V-1)(V-2)/2 v represents vertex and E the edges I think I need to disprove it with overall disproval but how?

## Removing vertices from a labelled graph

Let $$G$$ be an undirected graph with each vertex labeled with an integer. Is there an algorithm to remove a subset of vertices such that in the resulting graph with deleted vertices no vertices with different integer labels are connected with an edge, but also among all groups of vertices labeled with the same integer, the size of the smallest group (i.e., the number of vertices) is maximum possible?

Posted on Categories proxies

## How to check whether given $k$ vertices make a $k$-clique in an undirected graph $G$ efficiently

Let $$G=(V, E)$$ be an undirected graph with vertex set $$V$$ and edge set $$E$$. Let $$V’=\{v_1, v_2, …, v_k\}$$ be a subset of $$V$$ where degree of each $$v_i$$ is bigger than or equal to $$k$$. Is there a way to check whether $$V’$$ is a $$k$$-clique more efficient than the brute-force algorithm in $$O(k^2)$$? Thanks in advance.

Posted on Categories proxies

## Given undirected and connected graph G=(V,E). Prove for any DFS run: for any u,v∈V if u.d>v.d then u.d−v.d≥δ(u,v)

Given undirected and connected graph $$G = (V,E)$$. Prove for any DFS run: for any $$u,v \in V$$ if $$u.d>v.d$$ then $$u.d − v.d ≥ δ(u,v)$$

$$δ(u,v)$$-distance of a shortest path (not necessarily unique) in G

$$u.d,v.d$$-time, when each vertex was discovered in DFS for the first time.

I know that DFS not necessarily returns the shortest path.And I know that if $$u.d>v.d$$ then $$u$$ discovered after $$v$$, $$v≠u$$ and there is path is DFS between vertices, because G is connected.

I have tried to assume by contradiction that $$u.d-v.d<δ(u,v)$$

Given that G is connected and $$v.d. Then $$v$$ discovered before $$u$$ and $$u≠v$$. $$u.d-v.d$$ sets distance of some path from $$u$$ to $$v$$ in $$G_π$$. By our assumption this distance is smaller then $$δ(u,v)$$ and that is in contradiction to the fact that $$δ(u,v)$$ is a distance of a shortest path (not necessarily unique) in G.

But this prof is not full. Why can we say the “punch line”?

Posted on Categories proxies

## Graph theory: BFS (Breadth First Search) – why is current processed first?

I am referencing some code I found on GeeksForGeeks.com: Why is the current node printed (and processed) first before its children are processed? Wouldn’t “breadth first” mean “Process children first, then process parent”? or, is that only for Trees? I can’t be the only one to not understand this, so instead of flaming me, somebody please simply post the answer?

void Graph::DFSUtil(int v, bool visited[])  {      visited[v] = true; <-- why is this printed FIRST?     cout << v << " ";       // Recur for all the vertices adjacent      // to this vertex      list<int>::iterator i;      for (i = adj[v].begin(); i != adj[v].end(); ++i)          if (!visited[*i])              DFSUtil(*i, visited);  }   // DFS traversal of the vertices reachable from v.  // It uses recursive DFSUtil()  void Graph::DFS(int v)  {      // Mark all the vertices as not visited      bool *visited = new bool[V];      for (int i = 0; i < V; i++)          visited[i] = false;       // Call the recursive helper function      // to print DFS traversal      DFSUtil(v, visited);  }  
Posted on Categories proxies

## What is an example of a undirected, weighted graph that no matter where you start the resulting DFS-tree is not an MST?

Posted on Categories proxies

## Creating capacity graph for a list of flights?

I have a list of flights and for each flight, I have information like source, destination, flight capacity, arrival time, departure time. There are only 8 distinct values that are populated in the source and destination column. There are multiple flights between any two nodes, i.e. multiple flights from LAX to PHX and similarly multiple flights from PHX to other destinations. Now, I have to find the capacity of the whole network given our source is LAX and our destination is JFK. I am completely stuck on how to create a capacity graph or find the capacity of the whole network. Any idea or hint is greatly appreciated. Sample data

## Decomposition of graph to subgraphs according to parallel edges

I am supposed to calculate all-pair shortest path lengths of a graph. However, I first need the graph to be decomposed/expanded to a simple one based on the presence of parallel edges.

If N parallel edges exist between any two vertices A and B, I need to create N replicas of both vertices. Each replica of A will be connected to one and only one replica of B, and vice versa. In addition, all replicas of a vertex must be fully connected to each other.

As an example:-

 A === B

will become

 A1 ----- B1 |        | A2 ----- B2

Does this formulation match any well-defined graph theory problem? I am trying to come up with an algorithm that can make use of a GPU’s speed, since the graphs I am dealing with can become huge, and I am trying to do it by manipulating the adjacency matrix.

Posted on Categories proxies

## Proving that max flows of undirected graph and equivalent directed graph are equal

There is an undirected graph $$G$$. A graph $$H$$ is constructed by changing each edge $$(a,b)$$ in $$G$$ to a pair of directed edges $$(a,b)$$ and $$(b,a)$$. How to prove that the maximum flow in $$H$$ is equal to the maximum flow in $$G$$?

I don’t really have any idea how to start it. I just know that I can use Ford-Fulkerson on $$H$$ and update the reverse edge such that $$f(a,b)+f(b,a)=c(a,b)$$ but that’s it.

Posted on Categories proxies

## Graph of size n with girth >2k and minimum degree more than n^1/k

I’m stuck at a proof about Graphs in the context of Graph Spanners. A Lemma says:
Let $$G$$ be a graph with $$n$$ vertices and $$m$$ edges. If $$G$$ has girth more than $$2k$$, then $$m\leq n^{1+\frac{1}{k}}$$.
The proof is made by contradiction where repeatedly any node from $$G$$ of degree at most $$\lceil n^\frac{1}{k}\rceil$$ and any edges incident to that node is removed, until there is no such node anymore. This step leads to a subgraph $$G’$$ of $$G$$ of minimum degree more than $$\lceil n^\frac{1}{k}\rceil$$.
The conclusion is that $$G’$$ must have girth at most $$2k$$ and therefore also $$G$$, which is a contradiction.

I don’t understand the conclusion: Why must $$G’$$ have girth at most $$2k$$? Why is it not possible that $$G$$ has girth more than $$2k$$ and minimum degree more than $$\lceil n^\frac{1}{k}\rceil$$?

I don’t really see an answer to this question, so I would be very grateful if someone can help me.