1.7. Graph Isomorphism

Try these first

1. 1.

   Define what a subgraph is.

   Hint

   Remember that a subgraph must come from a larger graph.

2. 2.

   What is a proper subgraph?

   Hint

   Think about what 'proper' means in terms of inclusion.

3. 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.

   Hint

   Think about what 'proper' implies regarding size.

4. 4.

   True or False: Two graphs can be isomorphic if they have different numbers of edges.

   • True
   • False

   Hint

   Recall the definition of isomorphism.

5. 5.

   Design two undirected graphs that are isomorphic, then find a suitable bijection between their vertex sets.

   Hint

   Focus on maintaining edge connections when creating bijections.

6. 6.

   Create a graph exhibiting properties that prevent it from being isomorphic to another, focusing on unique vertex degrees.

   Hint

   Consider how vertex degrees affect the ability to find isomorphic matches.