1 Exercises Sheet1 Answers Std(1)(2)

I 2 2 0 5 : G ra p h Theory
Exercises- sheet1
New version Page19 corrected (bipartite graph)
Important Note
It is important to try solving exercises

yourself then read the given solution
just to correct your answer ....
Exercise 1- solution
Exercise 2
Exercise 2 - Solution
Exercise 2 - Solution
Exercise 3
Question 2: Deduce that the complement of a Bipartite graph is not necessarily bipartite
Exercise 3
Solution:
Exercise 4
Suppose you are a salesman, and you need to visit each village once.
→ How to do it given the below graph representing connection
between villages?
Answer
Hamiltonian graph
there are 2 ways you can complete the
desired routes
h d e c a b h or h d e c b a h
And their reverse order

habcedh or hbacedh
Total of 4 different travel itineraries.

Exercise 5
Suppose you have an ice-cream truck, and you want to pass by
route only once. → How to do it given the below graph representing
roads that can be passed?
Eulerian graph
Multiple solutions
5 3 1 2 4 3 6 10 9 8 4 7 9 6 7 10 5
5 10 9 8 4 2 1 3 6 10 7 9 6 7 4 3 5
Exercise 6
- Proof that Bipartite graph has no odd cycles.
Exercise 7
is A Isomorphic ?
they are equivalent graphs just in different forms.
S
Graphs G and H are isomorphic if there is a structure that preserves

a one-to-one correspondence btw the vertices and edges.
→ The 2 graphs differ only by the names of the edges and vertices
but are structurally equivalent.
1- Method One – Checklist

Look at the two graphs below. Are they isomorphic?
Ask the following questions:
1. Are the number of vertices in both graphs the same?

Yes, both graphs have 4 vertices.
2. Are the number of edges in both graphs the same?
Yes, both graphs have 4 edges.
3. Is the degree sequence in both graphs the same?
Yes, each vertex is of degree 2.
4. If the vertices in one graph can form a cycle of length k, can
we find the same cycle length in the other graph?
Yes, each graph has a cycle of length 4.
if we can answer yes to all four of the above questions, then the
graphs are isomorphic.
¨2- Method Two – Relabeling
show the following two graphs are isomorphic.
First, we check vertices and degrees and confirm that both graphs have 5 vertices and
the degree sequence in ascending order is (2,2,2,3,3).
Now we methodically start labeling vertices by beginning with the vertices of degree 3
and marking a and b.
Label Odd Vertices
Next, we notice that in both
graphs, there is a vertex that is
adjacent to both a and b, so we
label this vertex c in both
graphs.
Label Adjacent Vertex

This now follows that there are two vertices
left, and we label them according to d and e,
where d is adjacent to a and e is adjacent to
b.
Label Remaining Vertices
And finally, we define our
isomorphism by relabeling
each graph and verifying
one-to-correspondence.
Exercise 8: check if a graph is bipartite using the 2-coloring method.
Given the following graphs, determine if they are bipartite using the 2-
coloring method:
Graph 1:
A -- B
| |
C -- D General Approach
To check if a graph is bipartite using the 2-coloring method:
1.Start with any vertex and color it with color 1.
Graph 2: 2.Color all adjacent vertices with color 2.
A -- B 3.Continue coloring the graph such that no two adjacent vertices
| | have the same color.
4.If you can color the entire graph without conflicts, the graph is
C -- D bipartite. If you encounter a conflict, the graph is not bipartite.
| |
E -- F
Solution
Graph 1:
1.Start with vertex A and color it with color 1.
2.Color vertex B (adjacent to A) with color 2.
3.Color vertex C (adjacent to A) with color 2.
4.Color vertex D (adjacent to B and C) with color 1.
The coloring is as follows:
•A: Color 1
•B: Color 2
•C: Color 2
•D: Color 1
Since no two adjacent vertices have the same color, Graph 1 is
bipartite.
Graph 2:
1.Start with vertex A and color it with color 1.
2.Color vertex B (adjacent to A) with color 2.
3.Color vertex C (adjacent to A) with color 2.
4.Color vertex D (adjacent to B and C) with color 1.
5.Color vertex E (adjacent to C) with color 1.
6.Color vertex F (adjacent to D and E) with color 2.
The coloring is as follows:
•A: Color 1
•B: Color 2
•C: Color 2 G is bipartite
•D: Color 1
•E: Color 1
•F: Color 2
Since vertex C and vertex D are adjacent and both have color 2, Graph
2 is not bipartite.
Exercise 8’ : Check if these graphs are bipartite graphs using 2-coloring
method.
Bing Videos

1 Exercises Sheet1 Answers Std(1)(2)

Uploaded by

Copyright:

Available Formats

1 Exercises Sheet1 Answers Std(1)(2)

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

1 Exercises Sheet1 Answers Std(1)(2)

Uploaded by

Copyright:

Available Formats

I 2 2 0 5 : G ra p h Theory

It is important to try solving exercises

And their reverse order

Total of 4 different travel itineraries.

Graphs G and H are isomorphic if there is a structure that preserves

1- Method One – Checklist

1. Are the number of vertices in both graphs the same?

show the following two graphs are isomorphic.

Label Adjacent Vertex

You might also like