0
$\begingroup$

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 Answers 1

5
  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.

  • 0
    Nitpick: a nonconnected graph with no cycles is often called a "forest". I don't know if this definition is universal.2012-10-10