Scribd
Upload
12 views1 page

Graph Theory Homework Problems

The document contains a homework assignment focused on graph theory, with six problems related to graph isomorphism, non-isomorphic graphs, sequences, paths in graphs, cycles in 2-connected graphs, and a bonus proof regarding bipartite graphs. Each problem is assigned a specific point value and includes hints for solving them. The assignment references a textbook on discrete mathematics.

Uploaded by

rsdwivedi321
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views1 page

Graph Theory Homework Problems

The document contains a homework assignment focused on graph theory, with six problems related to graph isomorphism, non-isomorphic graphs, sequences, paths in graphs, cycles in 2-connected graphs, and a bonus proof regarding bipartite graphs. Each problem is assigned a specific point value and includes hints for solving them. The assignment references a textbook on discrete mathematics.

Uploaded by

rsdwivedi321
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

FOURTH HOMEWORK: INTRODUCTION TO GRAPH THEORY

1. (10pts) How many graphs on the vertex set {1, 2, . . . , 2n} are isomorphic to the graph
consisting of n vertex-disjoint edges (i.e. with edge set {{1, 2}, {3, 4}, . . . , {2n − 1, 2n}}?
Hint: At the first step, there are 2n − 1 ways to connect 1 to one of the vertices from
{2, . . . , 2n}. In general, at step i we try to connect the uncovered vertex of smallest index
Qn−1
to one of the remaning 2n − 2i − 1 vertices. Thus in total there are i=0 (2n − 1 − 2i) ways
to choose such isomorphic graphs.

2. (10pts) Draw all non-isomorphic 3-regular graphs on 6 vertices.


Hint: there are only two such graphs.

3. (10pts) Construct an example of a sequence of length n in which each term is some


of the numbers 1, 2, . . . , n − 1 and which has an even number of odd terms, and yet the
sequence is not a graph score.
Hint: for instance (1, 2, 3, 4, 5, 5).

4. (10pts) Let G be a graph in which all vertices have degree at least d. Prove that G
contains a path of length d (not necessarily an induced one).
Hint: starting from any vertex v1 , we choose any vertex v2 among the neighbors of v1 .
Next, we choose any v3 6= v1 from the neighbors of v2 (we can do so because d ≥ 2). In
general, at step i, if i ≤ d, then there is at least one neighbors vi+1 which is different from
v1 , . . . , vi−1 . This shows that the process terminates only when we already constructed a
path of at least d + 1 vertices.

5. (10 pts) Prove that for any two edges of a 2-connected graph, a cycle exists containing
both of them.
Hint: let e, e0 be any two edges of G. We sub-divide e, e0 by new points v, v 0 . The new
graph G0 clearly remains 2-connected. On the other hand, we have learned that there exists
a cycle in the new graph which contains v and v 0 . By definition, such cycles, when we
replace the edges ending at v and v 0 by e and e0 correspondingly, will contains both e, e0
and lie in G.
6* Bonus (20pts)* [1, 4.2.4] Prove that a graph is bipartite if and only if it contains no
cycle of odd length.
Hint: Without loss of generality, we can assume that the graph is connected. Start from
any vertex v0 of the graph, we divide the other vertices into groups N1 , N2 , . . . , where Ni
is the collection of vertices of distance i from v0 . The proof is complete if we can show the
following: (1) for any i ≥ 1, there are no edges within Ni ; (2) for any 1 ≤ i ≤ j with j at
least i + 2, there are no edges connecting Ni to Nj . The proofs of these two claims are not
difficult, basing on definition and on the property of not containing cycle of odd length.

References

[1] J. Matousek and J. Nesetril, Invitation to Discrete Mathematics, second edition.

You might also like