1
$\begingroup$

In an undirected unlabled graph $G=(V,E)$, we want to find a tree as a subgraph, such that the graph can be decomposed into edge disjoint trees(all the tress are isomorphic). How to define such a tree subgraph uniquely? For example, given degree sequence $(1,1)$, we immediately know that it is a path of length $1$.

It is known that every tree is bipartite. Isomorphic bipartite graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a bipartite graph; in some cases, non-isomorphic bipartite graphs may have the same degree sequence. Thus, degree sequence, alone, is not a good definition of such trees.

It is also known that Reconstructing a binary tree uniquely from its preorder and postorder traversals is impossible in general. http://www.cmi.ac.in/~madhavan/courses/programming06/lecture12-21sep2006.txt

$\endgroup$
1
  • $\begingroup$ Are you looking for spanning trees? -- But these are not unique, as a given graph may have many different spanning trees. $\endgroup$
    – Stefan Kohl
    Oct 17, 2015 at 12:29

1 Answer 1

5
$\begingroup$

It's not clear what sorts of definition you allow when you say "define a tree uniquely," but it seems that, under any reasonable notion of definability, a defined tree would be invariant under all automorphisms of the graph. Such a tree need not exist; the complete graph on three vertices is a counterexample.

Of course, if you allow additional structure, beyond just the graph $(V,E)$ to be used in the definition, then the situation cold be different, but then you should say what additional structure you have in mind.

$\endgroup$
0