0 votes

Give an example of a graph that contains at least 6 vertices, and each vertex has at least 4 neighbors, and the graph has a valid vertex coloring using only 2 colors.

in Graph Theory by AlgoMeister (1.6k points)

3 Answers

+4 votes
 
Best answer

I believe this bipartite graph will do. 

Connect 8 vertices, 4 on each side.  Each vertex is connected to vertices on the other side.

This should be the simplest possible answer, with 8 vertices total and 4 neighbors each.

by AlgoStar (416 points)
selected by
+2 votes

9 vertices, some vertices has 5 neighbors, and 2 colors (B: Blue) & (R: Red)

by AlgoMeister (920 points)
+1 vote
Please have a look at the below explanation, I have also tried to explain the graph representation through the adjacency matrix as well.

https://photos.google.com/share/AF1QipPHfLtZq6iE6BXxso_UCwU55cp5cNIcpDc0AC6YM4pkOJ9KMldP-avDcM0o_FG5Ig?key=NXBGZVI0TjM3Q19PX1NYUTNEbDRCS1ZYWXdBOHFn

Here, R1, R2, R3, R4 represents the RED edges and
B1, B2, B3, B4 represents the BLUE edges.
by (160 points)
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...