Complete graph

Encyclopedia : C : CO : COM : Complete graph

---

---

 

In the mathematical field of graph theory, a complete graph is a simple graph where an edge connects every pair of vertices. The complete graph on [n] vertices has [n] vertices and [n(n-1)/2] edges, and is denoted by [K_n]. It is a regular graph of degree [n-1]. All complete graphs are their own cliques. They are maximally connected as the only vertex cut which disconnects the graph is the complete set of vertices

A planar graph cannot contain [K_5] (or the complete bipartite graph [K_]) as a minor. Since [K_n] includes [K_], no complete graph [K_n] with [n] greater than or equal to 5 is planar.

Complete graphs on [n] vertices, for [n] between 1 and 8, are shown below:

Image:Complete graph K1.svg|[K_1] Image:Complete graph K2.svg|[K_2] Image:Complete graph K3.svg|[K_3] Image:Complete graph K4.svg|[K_4] Image:Complete graph K5.svg|[K_5] Image:Complete graph K6.svg|[K_6] Image:Complete graph K7.svg|[K_7] Image:Complete graph K8.svg|[K_8]

 

---

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

---

Search Titles

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

?