# Graph Theory - Clarification of type of graph

Just wondering if somebody can confirm the following:

1. If I have some number of verticies, if there is only one edge connecting two of the vertices, can this be a bipartite graph, or do all verticies need to be connected to make it a biartite graph?

2. If I have a graph, lets say 1-2-4-1-3, can this be a tree? My understanding is that it can not be a tree if it contains a cycle, but doesn't a cycle start and finish at the same vertix? I'm thinking it is a tree anyway.

I've been searching for these answers for the last hour. Any help would be very much appreciated.

-

## 1 Answer

1. A graph is bipartite if you can divide the vertices into two groups such that all the edges go from one group to the other. A bipartite graph might not have any edges; a graph with only one edge is always bipartite.

If every vertex in the first group is connected to every vertex in the other group, the graph is a "complete" bipartite graph. But not all bipartite graphs are complete.

2. A graph is a tree if it does not contain a cycle. If a graph contains a configuration like 1-2-4-1-3, then it also contains 1-2-4-1, which is a cycle, so the graph is not a tree.

I hope this clears up your questions.

-
Yes, thank you so much. – Sandra Oct 1 '12 at 13:32
Nitpick: a nonconnected graph with no cycles is often called a "forest". I don't know if this definition is universal. – Stefan Smith Oct 10 '12 at 17:30