Some special simple graphs
Example. The complete graph on n vertices, denoted by Kn, is the simple graph that contains exactly one edge between each pair of distinct vertices.
Example.
The cycle
,
consists of n
vertices
and edges
and
.
Example.
We obtain the wheel
Wn
when we add an additional vertex to the
cycle Cn,
for
,
and connect this new vertex to each of the n
vertices in Cn,
by new edges.
Example. The n-cube, denoted by Qn, is the graph that has vertices representing the 2n bit strings of length n. Two vertices are adjacent iff the bit strings that they represent differ in exactly one bit position.
Bipartite graphs
A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint nonempty sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2 (so that no edge in G connects either two vertices in V1 or two vertices in V2).
Example.
C6
is bipartite since its vertex set can be partitioned into the two
sets
and
,
and every edge of C6
connects a vertex in V1
and a vertex in V2.
Example. K3 is not bipartite. To see this, note that if we divide the vertex set of K3 into two disjoint sets, one of the two sets must contain two vertices. If the graph were bipartite, these two vertices could not be connected by an edge, but in K3 each vertex is connected to every other vertex by an edge.
Example. Are the graphs G and H bipartite?
Solution: Graph G is bipartite, since its vertex set is the union of two disjoint sets {a, b, d} and {c, e, f, g}, and each edge connects a vertex in one of these subsets to a vertex in the other subset. Note that for G to be bipartite it is not necessary that every vertex in {a, b, d} be adjacent to every vertex in {c, e, f, g}. For instance, b and g are not adjacent.
Graph H is not bipartite since its vertex set cannot be partitioned into two subsets so that edges do not connect two vertices from the same subset.
Example.
The complete bipartite graph
is the graph that has its vertex set partitioned into two subsets of
m and n
vertices, respectively. There is an edge between two vertices iff one
vertex is in the first subset and the other vertex is in the second
subset.
New graphs from old
When edges and vertices are removed from a graph, without removing endpoints of any remaining edges, a smaller graph is obtained. Such a graph is called a subgraph of the original graph.
A subgraph of
a graph
is a graph
where
and
.
The union
of two simple graphs
and
is the simple graph with vertex set
and edge set
.
The union of G1
and G2
is denoted by
.
Example. Find the union of the graphs G1 and G2.
Solution: The vertex set of the union is the union of the two vertex sets, namely, {a, b, c, d, e, f}. The edge set of the union is the union of the two edge sets.
Glossary
adjacent – соседний, смежный; pendant – подвесная, висячая; handshake – рукопожатие
bipartite – двусторонний; loop – петля