I've been studying graph theory recently and I find it very interesting. But since I'm studying it on my own, I feel like I'm missing something - for example, I'm struggling with these two problems:

  1. If for whichever two vertices a and b in the graph G there is only one simple path from a to b, then the graph is a tree.

Eh... isn't this part of the definition for a tree? I really don't even know where to start with proving this statements. I would really like to see a good proof laid out, so if anyone can help, please do! :)

Another one: 2. Find which complete bipartite graphs are complete.

What does it mean which COMPLETE bipartite graphs are complete? Can a complete bipartite graph not be complete? I would also love to see a good solution to this. It's really interesting and it bother's me that I can't solve it.

Any help is very much appreciated!

  • 3
    $\begingroup$ A complete graph has an edge between any two vertices. A complete bipartite graph has an edge between any two vertices on "opposite sides". $\endgroup$ – Lord Shark the Unknown May 10 '17 at 6:40
  • 2
    $\begingroup$ There are many equivalent definitions for a tree in graph theory. The solution of problem 1 will depend very much on just how trees are defined in your textbook. Instead of asking us what the definition of a tree is, why don't you tell us? $\endgroup$ – bof May 10 '17 at 7:09
  • 1
    $\begingroup$ For example, the graph $K_3$ is a complete graph which is not bipartite; the graph $P_4$ is bipartite but not complete, nor even complete bipartite; the graph $K_{2,2}$ aka $C_4$ is a complete bipartite graph, but not a complete graph; the graph $K_2$ aka $K_{1,1}$ is both a complete graph and a complete bipartite graph. $\endgroup$ – bof May 10 '17 at 7:21
  • 1
    $\begingroup$ @ParclyTaxel (1) is by definition if that's how trees are defined. If trees are defined as connected acyclic graphs, then (1) requires a proof. $\endgroup$ – bof May 10 '17 at 7:23
  • 1
    $\begingroup$ @ParclyTaxel That's a proof of the converse of the OP's problem 1. The OP has to prove that, if there are two different $uv$-paths, then there is a (simple) cycle in the graph. That's takes a bit more proving. $\endgroup$ – bof May 10 '17 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.