The following code snippet is to find the minimum possible degree of a graph whose number of vertices(n) and edges(e) are given.
The algorithm is such that a vertex can have maximum degree equal to (n-1) but if it is having degree 1 it means there is one more vertex whose degree is one and if its degree is 2 then there are 2 vertices whose degree is 1.
The here is the code for finding minimum degree of a graph
import java.io.*;
import java.util.Arrays;
public class MinDegree {
//function to find sum of an array
static int sum(int[] arr){
int sum = 0;
for(int a: arr){
sum += a;
}
return sum;
}
//function to find minimum of an array
static int minimum(int[] arr){
int min = Integer.MAX_VALUE;
for(int i=0; i<arr.length; i++){
if(arr[i] < min)
min = arr[i];
}
}
return min;
}
public static void main(String[] ar) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//number of edges should not exceed n(n-1)/2
System.out.println("Enter no of vertices and edges: n e");
String[] in = br.readLine().split(" ");//input should be like 5 7
int vertices = Integer.parseInt(in[0]);//parsing string into integers
int edges = Integer.parseInt(in[1]);
int[] degree = new int[vertices];//buffer to store degrees
int counter = 0;
int round = 0;
while(sum(degree) < (2*edges)){//sum of degrees must be less than 2*edges
if(degree[counter] < (vertices-1)){
degree[counter] += 1;
degree[round+counter+1] += 1;//it will increase neighbours degree
round++;
}
else{
counter++;
round = 0;
}
}
System.out.println(minimum(degree));
}
}
Happy Coding :)
