MHB Understanding Two Graph Theory Problems

[Puzzles]

Hi!

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.

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?

Any help is very much appreciated!

 

[Puzzles]

I actually managed to find an awesome proof for the first problem at slide 3 of http://www.math.ucsd.edu/~gptesler/184a/slides/184a_trees_17-handout.pdf

Now I've only to solve the second problem, if anyone has any hints, it would be grand. :)

 

[Evgeny.Makarov]

There are several equivalent definitions of a tree. Some of them are:

1. A connected acyclic graph.
2. A graph where every two vertices are connected by a single simple path.
3. A connected graph where every edge is a bridge (i.e., its removal makes the graph disconnected).
4. A connected graph with $n$ vertices and $n-1$ edges.
5. An acyclic graph with $n$ vertices and $n-1$ edges.

Concerning the second problem, a complete graph $K_n$ on $n$ vertices is a graph that has an edge between every pair of vertices. So I think the question means, for which $m$ and $n$ the complete bipartite graph $K_{m,n}$ is also $K_{m+n}$. The answer probably depends on whether $m$ and $n$ in $K_{m,n}$ can be zero.