Math 2.0

Combinatorics Example

Cycle graph

Example

Let n≥3n \ge 3 be an integer. The cycle graph CnC_n is the graph with vertex set ℤ/nℤ\mathbb{Z}/n\mathbb{Z} in which ii and jj are adjacent if and only if j−i=±1j - i = \pm 1. Its edges are {0,1},{1,2},…,{n−2,n−1}\{0, 1\}, \{1, 2\}, \dots, \{n-2, n-1\} and {n−1,0}\{n-1, 0\}.

Remarks

CnC_n has nn vertices and nn edges, and it is 22-regular and connected. C3C_3 is the complete graph K3K_3. The chromatic number of CnC_n is 22 for even nn and 33 for odd nn. The odd cycles are the obstruction in the theorem that a graph is bipartite iff it has no odd cycle.

Further reading

  1. Web https://en.wikipedia.org/wiki/Cycle_graph, lead section
About this page
Tag0QQ0F12962
URIm2://0QQ0F12962
Kindexample
WritingW2 usable
MSC05C38
Instance ofGraph
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W3

  • a person confirmed each agent-written section: rule P04 (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.