0 votes
Give an example of a graph that has all of the following properties.  (Note that you need to give a single graph as the answer.)
(i)    It is connected
(ii)    It has one articulation point.
(iii)    The graph needs at least 4 colors for a valid vertex coloring
(iv)    The graph does not have a 4-clique (that is, a clique of 4 vertices) as a subgraph.
in Graph Theory by AlgoMeister (1.6k points)
retagged by

1 Answer

+2 votes
 
Best answer

The following graph satisfies all the four conditions: 

The connected graph has an articulation point "3". Vertex coloring "4" as shown in image and has maximum clique of "3".

by AlgoMeister (584 points)
selected by
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...