# C++ Program to Perform Edge Coloring for the Complete Graph

This is a C++ program to perform edge coloring on a complete graph.

Problem Description

1. This algorithm performs edge coloring on a complete graph.
2. A complete graph is a graph which has a connecting edge between any pair of vertexes.

Problem Solution

1. This algorithm takes the input of the number of vertexes.
2. Construct a complete graph for v vertex.
3. It assigns a color to edges without assigning the same color to two adjacent edges.
4. Exit.

Program/Source Code

This is a C++ program to perform edge coloring on complete graph.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

```#include<iostream>

using namespace std;

// A function to color edges of the graph.
void EdgeColoring(int edge[][3], int e)
{
int i, col, j;
// Loop to assign a valid color to every edge 'i'.
for(i = 0; i < e; i++)
{
col = 1;
flag:
// Assign a color and then check its validity.
edge[i][2] = col;
for(j = 0; j < e; j++)
{
if(j == i)
continue;

// Check the colors of the edges adjacent to the edge i.
if(edge[j][0] == edge[i][0] || edge[j][0] == edge[i][1] || edge[j][1] == edge[i][0] || edge[j][1] == edge[i][1])
{
// If the color matches then goto line 11 and assign next color to the edge and check again.
if(edge[j][2] == edge[i][2])
{
col++;
goto flag;
}
}
}
}
}

int main()
{
int i, v, e, j, count = 0;

// take the input of the number of vertex and edges.
cout<<"Enter the number of vertexes for the complete graph: ";
cin>>v;

e = (v*(v-1))/2;
int edge[e][3];

// Construct a complete graph for the given number of edges.
for(i = 1; i <= v; i++)
{
for(j = i+1; j <= v; j++)
{
edge[count][0] = i;
edge[count][1] = j;
edge[count][2] = -1;
count++;
}
}

// Color the edges of the graph.
EdgeColoring(edge , e);

// Print the color of each edge.
for(i = 0; i < e; i++)
cout<<"\nThe color of the edge between vertex V(1):"<<edge[i][0]<<" and V(2):"<<edge[i][1]<<" is: color"<<edge[i][2]<<".";
}```
Program Explanation

1. Take the input of the number of vertexes ‘v’.
2. Construct a complete graph having e=v*(v-1)/2 edges, in edge[][].
3. Using EdgeColoring(), Color the graph edges.
4. Inside EdgeColoring(), assign color to current edge as col i.e. 1 initially.
5. If any of the adjacent edges have the same color then discard this color and go to flag again and try next color.
7. Exit.

Runtime Test Cases
```Case 1:
Enter the number of vertexes for the complete graph: 5

The color of the edge between vertex V(1):1 and V(2):2 is: color1.
The color of the edge between vertex V(1):1 and V(2):3 is: color2.
The color of the edge between vertex V(1):1 and V(2):4 is: color3.
The color of the edge between vertex V(1):1 and V(2):5 is: color4.
The color of the edge between vertex V(1):2 and V(2):3 is: color3.
The color of the edge between vertex V(1):2 and V(2):4 is: color2.
The color of the edge between vertex V(1):2 and V(2):5 is: color5.
The color of the edge between vertex V(1):3 and V(2):4 is: color1.
The color of the edge between vertex V(1):3 and V(2):5 is: color6.
The color of the edge between vertex V(1):4 and V(2):5 is: color7.

Case 2:
Enter the number of vertexes for the complete graph: 7

The color of the edge between vertex V(1):1 and V(2):2 is: color1.
The color of the edge between vertex V(1):1 and V(2):3 is: color2.
The color of the edge between vertex V(1):1 and V(2):4 is: color3.
The color of the edge between vertex V(1):1 and V(2):5 is: color4.
The color of the edge between vertex V(1):1 and V(2):6 is: color5.
The color of the edge between vertex V(1):1 and V(2):7 is: color6.
The color of the edge between vertex V(1):2 and V(2):3 is: color3.
The color of the edge between vertex V(1):2 and V(2):4 is: color2.
The color of the edge between vertex V(1):2 and V(2):5 is: color5.
The color of the edge between vertex V(1):2 and V(2):6 is: color4.
The color of the edge between vertex V(1):2 and V(2):7 is: color7.
The color of the edge between vertex V(1):3 and V(2):4 is: color1.
The color of the edge between vertex V(1):3 and V(2):5 is: color6.
The color of the edge between vertex V(1):3 and V(2):6 is: color7.
The color of the edge between vertex V(1):3 and V(2):7 is: color4.
The color of the edge between vertex V(1):4 and V(2):5 is: color7.
The color of the edge between vertex V(1):4 and V(2):6 is: color6.
The color of the edge between vertex V(1):4 and V(2):7 is: color5.
The color of the edge between vertex V(1):5 and V(2):6 is: color1.
The color of the edge between vertex V(1):5 and V(2):7 is: color2.
The color of the edge between vertex V(1):6 and V(2):7 is: color3.```

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

If you find any mistake above, kindly email to [email protected]