# This graph is basically a concatenation of two star graphs
#
#     1           6
#      \         /
#       \       /
#  2 --- 3 --- 5 --- 7
#       /       \
#      /         \
#     4           8
#
# The minimum vertex cover is {3, 5} that covers all edges

1 3
2 3
4 3
6 5
7 5
8 5
