Description

The Final Recitation
What is isomorphism?
The simple graphs G1 = (V1,E1) and G2 = (V2,E2) are isomorphic if there exists a one-to-one and onto function f from V1 to V2 with the property that a and b are adjacent in G1 if and only if f(a) and f(b) are adjacent in G2, for all a and b in V1. Such a function f is called an isomorphism. Two simple graphs that are not isomorphic are called nonisomorphic.
Questions
1. Show that isomorphism of simple graphs is an equivalence relation.

2. Suppose that G and H are isomorphic simple graphs. Show that their complementary graphs G and H are also isomorphic.
3. Determine whether the given pair of graphs is isomorphic. Exhibit an isomorphism or provide a rigorous argument that none exists.
(b) Part b
(a) Part a
4. Determine whether each given graph has an Euler circuit. Construct such a circuit when one exists. If no Euler circuit exists, determine whether the graph has an Euler path and construct such a path if one exists. exists.
Definition: An Euler circuit in a graph G is a simple circuit containing every edge of G. An Euler path in G is a simple path containing every edge of G.
Theorem 1: A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree
1
CS 113 Spring 201 Recitation: Graphs The Final Recitation

Theorem 2: A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.

5. A graph with maximum degree at most k is (k + 1)-colorable
6. Show that Kn has a Hamiltonian circuit whenever n ≥ 3
Dishes: Ramen, Qeema samosas, Aloo ke pakorey, hash browns, Fish Fingers, Pizza, Pork
Haania likes Aloo ke pakorey and Qeema samosas
Ifrah likes Ramen, fish fingers
Mujtaba likes Qeema samosas, Hash browns and fish fingers
Affan likes Aloo ke pakorey
Is it possible? Show using the Hall Marriage Theorem. If there is, mention what is that matching.

Page 2 of 3
CS 113 Spring 201 Recitation: Graphs The Final Recitation

1 Message from the TAs
From Affan: Dear people who have taken discrete mathematics this semester. I was asked to share some departing words and advice with you all. In which regard I must firstly congratulate all of you for putting in relentless effort that this course required. I hope that apart from technical skills like latex, logic and proofs you were also able to take away soft skills like communication, team work and time management. I would request all of you to value and work on your these skills throughout your 4 years at Habib. My advice for people has always been specific to their circumstances and now that I have to give general advice the job is much tougher. Perhaps the best advice I can give is be a good person, actively self reflect on your values and actions and try to make change wherever necessary. Look after the people around you, the plants, the animals and be empathetic. Always assume people have good intentions and make respectable decisions that don’t compromise your values. Above all try to do the things that bring you joy.

Page 3 of 3