Editing Graph (discrete mathematics) (section)

== Types of graphs ==
=== Oriented graph ===
One definition of an ''oriented graph'' is that it is a directed graph in which at most one of {{nowrap|(''x'', ''y'')}} and {{nowrap|(''y'', ''x'')}} may be edges of the graph. That is, it is a directed graph that can be formed as an [[orientation (graph theory)|orientation]] of an undirected (simple) graph. 

Some authors use "oriented graph" to mean the same as "directed graph".  Some authors use "oriented graph" to mean any orientation of a given undirected graph or multigraph.

=== Regular graph ===
{{main|Regular graph}}
A ''regular graph'' is a graph in which each vertex has the same number of neighbours, i.e., every vertex has the same degree. A regular graph with vertices of degree ''k'' is called a ''k''‑regular graph or regular graph of degree ''k''.

=== Complete graph ===
{{main|Complete graph}}
[[File:Complete graph K5.svg|thumb|upright|A complete graph with five vertices and ten edges. Each vertex has an edge to every other vertex.]]

A ''complete graph'' is a graph in which each pair of vertices is joined by an edge. A complete graph contains all possible edges.

=== Finite graph ===
A ''finite graph'' is a graph in which the vertex set and the edge set are [[finite set]]s. Otherwise, it is called an ''infinite graph''.

Most commonly in graph theory it is implied that the graphs discussed are finite. If the graphs are infinite, that is usually specifically stated.

=== Connected graph ===
{{main|Connectivity (graph theory)}}
In an undirected graph, an unordered pair of vertices {{nowrap|{{mset|''x'', ''y''}}}} is called ''connected'' if a path leads from ''x'' to ''y''. Otherwise, the unordered pair is called ''disconnected''.

A ''connected graph'' is an undirected graph in which every unordered pair of vertices in the graph is connected. Otherwise, it is called a ''disconnected graph''.

In a directed graph, an ordered pair of vertices {{nowrap|(''x'', ''y'')}} is called ''strongly connected'' if a directed path leads from ''x'' to ''y''. Otherwise, the ordered pair is called ''weakly connected'' if an undirected path leads from ''x'' to ''y'' after replacing all of its directed edges with undirected edges. Otherwise, the ordered pair is called ''disconnected''.

A ''strongly connected graph'' is a directed graph in which every ordered pair of vertices in the graph is strongly connected. Otherwise, it is called a ''weakly connected graph'' if every ordered pair of vertices in the graph is weakly connected. Otherwise it is called a ''disconnected graph''.

A ''[[k-vertex-connected graph]]'' or ''[[k-edge-connected graph]]'' is a graph in which no set of {{nowrap|''k'' − 1}} vertices (respectively, edges) exists that, when removed, disconnects the graph. A ''k''-vertex-connected graph is often called simply a ''k-connected graph''.

=== Bipartite graph ===
{{main|Bipartite graph}}
A ''[[bipartite graph]]'' is a simple graph in which the vertex set can be [[Partition of a set|partitioned]] into two sets, ''W'' and ''X'', so that no two vertices in ''W'' share a common edge and no two vertices in ''X'' share a common edge. Alternatively, it is a graph with a [[chromatic number]] of 2.

In a [[complete bipartite graph]], the vertex set is the union of two disjoint sets, ''W'' and ''X'', so that every vertex in ''W'' is adjacent to every vertex in ''X'' but there are no edges within ''W'' or ''X''.

=== Path graph ===
{{main|Path graph}}
A ''path graph'' or ''linear graph'' of order {{nowrap|''n'' ≥ 2}} is a graph in which the vertices can be listed in an order ''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub> such that the edges are the {{nowrap|{{mset|''v''<sub>''i''</sub>, ''v''<sub>''i''+1</sub>}}}} where ''i'' = 1, 2, …, ''n'' − 1. Path graphs can be characterized as connected graphs in which the degree of all but two vertices is 2 and the degree of the two remaining vertices is 1. If a path graph occurs as a [[Glossary of graph theory#Subgraphs|subgraph]] of another graph, it is a [[Path (graph theory)|path]] in that graph.

=== Planar graph ===
{{main|Planar graph}}
A ''planar graph'' is a graph whose vertices and edges can be drawn in a plane such that no two of the edges intersect.

=== Cycle graph ===
{{main|Cycle graph}}
A ''cycle graph'' or ''circular graph'' of order {{nowrap|''n'' ≥ 3}} is a graph in which the vertices can be listed in an order ''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub> such that the edges are the {{nowrap|{{mset|''v''<sub>''i''</sub>, ''v''<sub>''i''+1</sub>}}}} where ''i'' = 1, 2, …, ''n'' − 1, plus the edge {{nowrap|{{mset|''v''<sub>''n''</sub>, ''v''<sub>1</sub>}}}}. Cycle graphs can be characterized as connected graphs in which the degree of all vertices is 2. If a cycle graph occurs as a subgraph of another graph, it is a cycle or circuit in that graph.

=== Tree ===
{{main|Tree (graph theory)}}
A ''tree'' is an undirected graph in which any two [[Vertex (graph theory)|vertices]] are connected by ''exactly one'' [[Path (graph theory)|path]], or equivalently a [[Connected graph|connected]] [[Cycle (graph theory)|acyclic]] undirected graph.

A ''forest'' is an undirected graph in which any two vertices are connected by ''at most one'' path, or equivalently an acyclic undirected graph, or equivalently a [[Disjoint union of graphs|disjoint union]] of trees.

=== Polytree ===
{{main|Polytree}}

A ''polytree'' (or ''directed tree'' or ''oriented tree'' or ''singly connected network'') is a [[directed acyclic graph]] (DAG) whose underlying undirected graph is a tree.

A ''polyforest'' (or ''directed forest'' or ''oriented forest'') is a directed acyclic graph whose underlying undirected graph is a forest.

=== Advanced classes ===
More advanced kinds of graphs are:
* [[Petersen graph]] and its generalizations;
* [[perfect graph]]s;
* [[cograph]]s;
* [[chordal graph]]s;
* other graphs with large [[Graph automorphism|automorphism groups]]: [[Vertex-transitive graph|vertex-transitive]], [[Arc-transitive graph|arc-transitive]], and [[distance-transitive graph]]s;
* [[strongly regular graph]]s and their generalizations [[distance-regular graph]]s.