Graph Coloring- Part 1

Discrete Mathematics Level 3

A graph is a collection of vertices (points) joined by edges (line segments). A pair of vertices are adjacent if they are connected by an edge.

Coloring a graph refers to assigning colors to its vertices. A graph is said to be properly colored if every pair of adjacent vertices receive different colors.

Consider the above graph with 4 vertices and 4 edges. This graph is denoted as \(C_{4} \). If you are permitted to use 6 different colors, how many proper coloring does \(C_{4} \) have ?

1. Vertices are adjacent if they are joined by an edge (line).
2.The coloring that is in the figure is an example of proper coloring.


Problem Loading...

Note Loading...

Set Loading...