# What makes is the difference between a tree and a graph?

I have seen in some text books that they have started talking about a tree and then they use the terms such as vertices and edges and treat is as a graph.

What makes a graph a graph and what makes a tree a tree? I am getting the impression that a tree is a subset of a graph but what are these properties that make a graph a tree?

Is there a way to classify a graph from a tree?

• Trees are connected Graphs without cycles. – Aristu Oct 22 '16 at 20:05
• Did you have a look on Wikipedia? – Juho Oct 22 '16 at 20:22
• is that it? what about the type of edges they have? Are cross edges allowed? Can one node have two parents? – user1932405 Oct 22 '16 at 20:41
• You can always draw a tree without crossings. And yes a node may have more than a single parent. You can also think of (connected) trees as any graphs of |V|+1 edges, where |V| is the number of vertices. – jgyou Oct 22 '16 at 20:50
• @jgyou You mean $|V|-1$ edges. – Yuval Filmus Oct 22 '16 at 21:59

## 1 Answer

An unrooted tree is a connected acyclic graph, that is a graph in which any two vertices are connected, and which contains no cycles. In particular, it's a graph.

A rooted tree is a tree in which one of the vertices has been designated as root. Every other vertex has a parent, which is its unique neighbor closer to the root. Its other neighbors are known as its children.

• can you please clarify what kind of edges a tree and a graph can have? Also by your definition of "unique neighbour" does that mean that tree children must have a single unique parent? – user1932405 Oct 22 '16 at 22:13
• Yes, but I bet that Wikipedia did a better job. In short, though, a graph is specified by a set of vertices, and for every two vertices $x,y$, whether the edge $(x,y)$ exists or not. That's all. Graphs do not come with any kind of drawing. – Yuval Filmus Oct 22 '16 at 22:14
• yes thats fine but what I mean is tree-edges, back-edges and cross-edges I was under the impression you could only have tree edges in a tree, is that true? – user1932405 Oct 22 '16 at 22:20
• This terminology comes from the DFS algorithm, and describes its output. DFS indeed finds a spanning tree in every connected graph. A tree would indeed have only tree-edges in the classification produced by DFS. – Yuval Filmus Oct 22 '16 at 22:23
• Right, a connected graph is a tree if DFS only finds tree-edges. – Yuval Filmus Oct 22 '16 at 22:30