Practice Vertex Chromatic Number (4.6.1) - Prof. Ashish Choudhury - Discrete Mathematics

Practise this section

9 questions

Flashcard drill
2 cards from this section. Quick, good the night before a test.
Exercise
6 questions · about 4 min · pass mark 70%. Hints available.
Sign up to start the exercise
Quiz
3 questions · about 2 min · pass mark 70%. Hints available.
Sign up to start the quiz

6 sample questions

Question 1.
What is the vertex connectivity of a complete graph with 4 vertices?
Show hintHide hint
How many vertices do you need to remove to disconnect the graph?
Question 2.
Define edge connectivity.
Show hintHide hint
Think about how many edges you would need to cut.
3Question 3.
What is vertex connectivity?
- Number of edges to disconnect a graph
- Number of vertices to disconnect a graph
- Minimum degree of a vertex
Show hintHide hint
Consider how we define connectivity.
4Question 4.
True or False: Edge connectivity can be less than vertex connectivity.
- True
- False
Show hintHide hint
Review the definitions carefully.
Question 5.
Construct a non-complete graph with vertex connectivity 2, edge connectivity 2, and a minimum degree of 2. Explain your reasoning.
Show hintHide hint
Ensure connectivity conditions are met while keeping it non-complete.
Question 6.
Prove that for any simple graph with n vertices, the maximum degree is at least n-1.
Show hintHide hint
Use a connectivity argument to support degree calculations.

5 more questions in this section. Enroll free to practise them all.