# Two graph theory problems

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!

• A complete graph has an edge between any two vertices. A complete bipartite graph has an edge between any two vertices on "opposite sides". – Lord Shark the Unknown May 10 '17 at 6:40
• 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? – bof May 10 '17 at 7:09
• 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. – bof May 10 '17 at 7:21
• @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. – bof May 10 '17 at 7:23
• @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. – bof May 10 '17 at 7:44