PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very low Entry average rating: No information on entry rating
complete graph (Definition)

The complete graph with $ n$ vertices, denoted $ K_n$, contains all possible edges; that is, any two vertices are adjacent.

The complete graph of $ 4$ vertices, or $ K_4$ looks like this:

\includegraphics[scale=1.0]{k4.eps}

The number of edges in $ K_n$ is the $ n-1$th triangular number. Every vertex in $ K_n$ has degree $ n-1$; therefore $ K_n$ has an Euler circuit if and only if $ n$ is odd. A complete graph always has a Hamiltonian path, and the chromatic number of $ K_n$ is always $ n$.



"complete graph" is owned by vampyr.
(view preamble)

View style:

See Also: tournament

Other names:  complete, clique
Log in to rate this entry.
(view current ratings)

Cross-references: chromatic number, Hamiltonian path, odd, Euler circuit, degree, triangular number, adjacent, edges, contains, vertices
There are 27 references to this entry.

This is version 6 of complete graph, born on 2002-02-03, modified 2002-05-27.
Object id is 1757, canonical name is CompleteGraph.
Accessed 9640 times total.

Classification:
AMS MSC05C99 (Combinatorics :: Graph theory :: Miscellaneous)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)