Question 36
An articulation point (cut vertex) in a connected graph is a vertex whose removal:
By definition, removing an articulation point (and its associated edges) disconnects the graph into two or more components.
An articulation point (cut vertex) in a connected graph is a vertex whose removal:
By definition, removing an articulation point (and its associated edges) disconnects the graph into two or more components.
What is the chromatic number of a complete graph $K_{n}$?
In $K_{n}$, every vertex is connected to every other vertex. Thus, no two vertices can share the same color, requiring n distinct colors.
What is the chromatic number of a bipartite graph with at least one edge?
A bipartite graph with at least one edge is not edgeless, so both parts are nonempty and two colors are necessary and sufficient.
What is the chromatic number of a cycle graph $C_{n}$ with an ODD number of vertices (n >= 3)?
An odd cycle is not bipartite and cannot be colored with 2 colors; alternating colors around the cycle forces a conflict, so exactly 3 colors are required.
What is the chromatic number of a cycle graph $C_{n}$ with an EVEN number of vertices (n >= 4)?
An even cycle is bipartite, so its vertices can be colored alternately with exactly 2 colors.