Practice Graph Isomorphism (1.7) - Various Operations on Graphs - Discrete Mathematics

Practise this section

8 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
2 questions · about 1 min · pass mark 70%. Hints available.
Sign up to start the quiz

6 sample questions

Question 1.
Define what a subgraph is.
Show hintHide hint
Remember that a subgraph must come from a larger graph.
Question 2.
What is a proper subgraph?
Show hintHide hint
Think about what 'proper' means in terms of inclusion.
3Question 3.
What is a proper subgraph?
- A subgraph that contains all vertices and edges.
- A subgraph that contains fewer vertices and edges than the original.
- A graph that is equal to its parent.
Show hintHide hint
Think about what 'proper' implies regarding size.
4Question 4.
True or False: Two graphs can be isomorphic if they have different numbers of edges.
- True
- False
Show hintHide hint
Recall the definition of isomorphism.
Question 5.
Design two undirected graphs that are isomorphic, then find a suitable bijection between their vertex sets.
Show hintHide hint
Focus on maintaining edge connections when creating bijections.
Question 6.
Create a graph exhibiting properties that prevent it from being isomorphic to another, focusing on unique vertex degrees.
Show hintHide hint
Consider how vertex degrees affect the ability to find isomorphic matches.

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