Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 5 down vote accepted
  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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.