1
$\begingroup$

Is it correct to say that:

"A complete graph is a graph in which each vertex is connected to all other vertices in the graph"

That's how I always thought about it, the official definition is different (I know that).

$\endgroup$
1
  • 3
    $\begingroup$ It would be better to change "connected" to "adjacent", since "connected" can be interpreted as "belonging to the same connected component", meaning only that its possible to get from one vertex to another by some path, rather than a single edge. $\endgroup$ Dec 11, 2018 at 16:33

3 Answers 3

3
$\begingroup$

I'm not sure what "official definition" you have in mind but your definition of a complete graph is correct: it implies that every pair of distinct vertices are connected by an edge.

At least, it does assuming that by "connected", you mean "has an edge to". It's best to avoid using the word in that way, since "connected" in graph theory refers to the existence of paths that might be longer than a single edge.

$\endgroup$
0
$\begingroup$

Yes, if you just want to talk about a property of complete graph, in which case, it is better to avoid using "A complete graph is ...". It will be clear and unambiguous if you say, in a complete graph, each vertex is connected to all other vertices.

No, if you did mean a definition of complete graph. For example, all vertice in the 4-cycle graph as show below are pairwise connected. However, it is not a complete graph since there is no edge between its middle two points.

3-cycle, 4-cycle and a 5-cycle from math.stackexchange.com/questions/24475

We can review the definitions in graph theory below, in the case of undirected graph.

A path from $x$ to $y$ is a finite of edges which connect a sequence of vertices which, by most definitions, are all distinct from one another.

An unordered pair of vertices {x, y} is called connected if a path leads from x to y. Otherwise, the unordered pair is called disconnected.

A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge

You may have been thinking that a vertex is connected to another only when there is an edge between them. While that is correct in ordinary English, you would better stick to the general convention and terminologies in the graph theory, where two vertices is connected is defined as above.

There is another way to think about complete graph. For each edge {x, y}, the vertices x and y are said to be adjacent to one another. As j_random_hacker suggested, we can say "A complete graph is a graph in which each vertex is adjacent to all other vertices in the graph".


Exercise: Is the 3-cycle graph a complete graph? Is the 5-cycle graph a complete graph?

$\endgroup$
0
$\begingroup$

Assume each edge's weight is 1. A complete graph is a graph which has eccentricity 1, meaning each vertex is 1 unit away from all other vertices. So, as you put it, "a complete graph is a graph in which each vertex has edge with all other vertices in the graph."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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