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.

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<u.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”?

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.

Number of spanning trees in undirected simple graph


What is the number of spanning trees in an undirected simple graph?

My attempt:

Let $ m$ be the number of edges in a simple graph, and let $ n$ be the number of vertices.

Then number of spanning trees is $ \binom{m}{n-1}$ minus the number of cycles of length $ n-1$ .

I read on Wikipedia that the number of spanning trees in the complete graph $ K_n$ is $ n^{n-2}$ .

According to the formula I stated above, it should be $ \binom{n(n-1)/2}{n-1} – \binom{n}{n-1} (n-1)!$ .

How do I show that this is equal to $ n^{n-2}$ for $ K_n$ ?

How to deal with parallel edges between two vertices in cycle detection using BFS in an undirected graph?

I am new to Programming and learning Algorithms and was studying BFS when I read that BFS could be used for cycle detection. I tried to implement the same on an undirected graph G with Adjacency List Representation. What I did is as follows:

• Do a simple BFS Traversal using a Queue while maintaining the parent node of nodes enqueued in the queue.

• If I come across a node u that has a neighbor v such that v is already visited but v is not the parent of u then that means there is cycle in the graph.

Pseudocode:

#adjList is the adjacency list given as a dictionary #myQueue is a double-sided queue containing node and its parent node ([Node, parNode]) #visited is a set containing visited nodes  while(myQueue):     currNode, parNode = myQueue.pop() #dequeue operation     visited.add(currNode) #Marking currNode as visited     for childNode in adjList[currNode]: #Traversing through all children of currNode         if currNode not in visited:             myQueue.appendleft([childNode, currNode]) #Enqueue operation         else:             if childNode!=parNode: #Main logic for cycle detection                 print('CYCLE DETECTED')                 break 

The above approach is working except in cases when I have more than 1 edge between 2 vertices for e.g. in following case we have 2 edges between vertices 0 and 1:

Graph containing cycle

Adjacency list of above graph is: adjList = {0:[1, 2], 1:[0], 2:[0]}. Here we can clearly see that the graph contains a cycle but above algorithm is not able to detect the same because when BFS will reach vertex 1, vertex 0 is already visited but vertex 0 is also the parent of vertex 1 so this cycle will go undetected.

My question is how I can modify above algorithm to detect such cases?

Edit: I tried the same logic on directed graphs also, and I am facing similar problem i.e. case when I have a directed edge from vertex 0 to vertex 1 and another directed edge from vertex 1 to vertex 0

Forward edges in undirected grapth using BFS

Introduction to Algorithms books claims BFS only classifies an edge for an undirected graph to be either tree or cross edge. But how about this simple example below where forward edges are naturally appearing?

Given graph with just 2 vertices A and B and 3 edges from A to B!

exploring A adjacent vertices

(1) A->B (tree edge, A is now marked as an ancestor for B and B is A’s descendant)

(2) A->B (forward edge? B is not yet processed (gray) and we found an edge to it from its ancestor(A))

(3) A->B forward edge using the same reasoning as in (2)!

What am I missing here?

Average branching factor of an undirected graph

I’m trying to determine, given an unweighted undirected graph, the maximum number of leaves of any travelling of the graph, which means, the maximum number of leaves among all traversals of every spanning tree of the graph.

I know that, given a tree of $ n$ nodes, an average branching factor $ b_f$ and $ n_l$ leaf nodes, these three variables are related as follow:

$ $ b_f = \frac{e}{n-n_l} \Rightarrow n_l = n – \frac{e}{b_f}$ $

where $ e = n – 1$ (the number of edges).

However, if instead of an undirected tree you have an undirected graph of $ n$ nodes and $ e = n – 1 + k$ edges (or with $ k$ fundamental cycles), different traversals of the graph would give you different spanning trees, depending on which one of those $ k$ edges are the one being ignored from the graph.

Also, I don’t have a clear picture about how to calculate the “branching factor” of a graph since nodes have not notion of “parent node”, because their outdegrees are not known until some traversal starts, but I need to considered “any” traversal, specifically, a worst case scenario where any not-known-yet traversal have a maximum number of leaves.

Is there any known property of graph’s spanning trees that can offer an upper bound on the number of resulting leaves nodes of any traversal?

My best approximation so far is that, the maximum number of leaves must be bounded by $ $ n_l <= |\{n_{e^1}\}| + 2k$ $ where $ |\{n_{e^1}\}|$ is the number of nodes of the graph with degree 1, and $ k = e – n + 1$ .

That’s a worst case scenario where there exists $ k$ edges in the graph connecting nodes with degree 2 each, because removing them will give $ 2k$ nodes with degree 1 each, and thus $ + 2k$ leaves. If $ k$ is very low that can be an acceptable good approximation, but the biggest the connectivity of the graph, the worst the significance of the approximation.

If someone could give a better approximation based on the average degree of the graph or something similar that can be calculated on a first traversal would be appreciated.

UNDIRECTED HAMCYCLE to HAMPATH reduction

I’ll define the problems

UHAMPATH

Input: A undirected graph G and 2 nodes, s and t

Question: Is there a hamiltonian path from s to t in G?

UHAMCYCLE

Input: A undirected graph G

Question: Is there a hamiltonian cycle in G?

$ $ UHAMCYCLE \leq_p UHAMPATH$ $

my reduction is as followed $ (G) \to (G’, s, t)$

function(G)      for each e = (u, v) in E(G)         G' = G         add nodes u' and v' to G'         add edges (u', u) and (v, v')         s = u'         t = v'         if there is a hamilton path from s to t:             return (G', s, t) 

Basically if there is a hamilton cycle in G then some edge in $ G$ will form a hamilton path in $ G’$ .

An example to further illustrate the reduction:

 Graph G  (a) ---- --(d)  | \        |  |   \      |  |    \     |  |     \    |   |      \   |   |       \  |  |         \|      | (b) ------ (c)  Has a clear Hamilton cycle (a, b, c, d).   If we choose edges (a, d)   Graph G'  (s)--(a) ---- --(d)       | \        |       |   \      |       |    \     |       |     \    |        |      \   |        |       \  |       |         \|            (b) ------ (c)--(t) 

Doesn’t have a hamilton path from s to t. However if you choose any other edge such as (a, d) then

(s)--(a) ---- --(d)--(t)       | \        |       |   \      |       |    \     |       |     \    |        |      \   |        |       \  |       |         \|            (b) ------ (c) 

$ (s \to a \to b \to c \to d \to t)$ . Holds.


I’m confused whether or not I can use this line:

if there is a hamilton path from s to t:     return (G', s, t) 

Checking to see if a graph has a hamilton path is NP complete but since we are looking to reduce it to it I think we can?