Find two graphs with the same score, but one is a tree and the other is not a tree
The question is pretty self-explanatory: Find a tree and a non-tree which have the same graph score. (The score of the graph is a sequence of the degrees of the graph from smallest to the largest)
I am thinking about one thing:
A graph is a tree when it is cyclic and connected. So if I want to make a graph which is not a tree, I think I should use the acyclic property of the tree
Solution 1:
Well, I found it. This is the second easiest solution. The tree is:
O-O-O-O-O-O
with the score of $1,1,2,2,2,2$.
The non-tree is:
O-O-O
O
/ \
O - O
for which the score is $1,1,2,2,2,2$.
The simplest is (thanks to Stinking Bishop):
Tree:
O-O-O-O-O
The other graph:
O-O
O
/ \
O - O
Their score is $1,1,2,2,2$