Common Graph Classes

A graph G is called a path if its vertices can be (re)labeled u₁, u₂, ..., u_n so that its edges are u₁u₂, u₂u₃, ..., u_n-1u_n.

P_n

A graph G is called complete if every pair of distinct vertices is adjacent.

<p>K_n</p> Signup and view all the answers

<p>$m = \binom{n}{2} = \frac{n(n-1)}{2}$</p> Signup and view all the answers

<p>The complement of a graph G, denoted by G, is the graph with vertex set V(G) such that for each pair of distinct vertices u, v of G, uv is an edge of G iff uv is not an edge of G.</p> Signup and view all the answers

<p>$m¯ = \binom{n}{2} - m = \frac{n(n-1)}{2} - m$</p> Signup and view all the answers

<p>K_n has n vertices but zero edges and is called the empty graph of order n.</p> Signup and view all the answers

<p>A graph G = (V, E) is bipartite if the vertex set V can be partitioned into two sets A and B (the bipartition or partite sets) such that no edge in E has both endpoints in the same set of the bipartition.</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>The join G + H is the graph that consists of G ∪ H and all edges joining a vertex of G and a vertex of H.</p> Signup and view all the answers

<p>The Cartesian Product G × H is the graph with vertex set V(G × H) = V(G) × V(H). Two distinct vertices (u, v) and (x, y) are joined by an edge if either a) u = x and vy ∈ E(H), or b) v = y and ux ∈ E(G),</p> Signup and view all the answers

<p>Replace each x ∈ E(G) by a copy of the graph H, call it H_x. Then, join corresponding vertices of H_x and H_y if x and y are adjacent in G. Otherwise, we do not add any edges between H_x and H_y.</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

A graph where vertices are labeled to create a linear connection.

A graph where vertices form a closed loop with edges connecting in sequence.

A graph where every pair of distinct vertices is adjacent.

The number of edges in a graph, calculated for complete graphs as m=n(n-1)/2.

A graph that represents absence of edges; edges exist if they are not in G.

A graph whose vertices can be split into two sets with no edges within each set.

A nontrivial graph is bipartite if it contains no odd cycles.

Two sets (A and B) that divide the vertex set of a bipartite graph.

A cycle containing an odd number of vertices, which prevents bipartitioning.

Graph formed by combining G and H with edges connecting their vertices.

A graph where vertices from G and H create a new vertex set with specific edges.

The number of vertices in a graph.

A complete graph with zero edges, consisting only of vertices.

The degree of a vertex is the number of edges incident to it.

A graph that has at least one edge (not just isolated vertices).

A logical approach showing that assuming the opposite leads to an impossibility.

A line connecting two vertices in a graph.

A fundamental unit by which graphs are formed, often represented as points.

A graph in which there is a path between every pair of vertices.

Different points in a graph with unique identifiers.

The shortest route that connects two points in a graph.

If G has order n and size m, Ḡ has order n and size n(n-1)/2 - m.

Dividing graph's vertices into two groups where edges only exist between groups.

Different ways to illustrate or depict the same graph structure.

The two separate sets in a bipartite graph arrangement (A and B).

A method of proving a statement is true by showing that assuming it false leads to an incongruence.

A path in a graph that visits every edge exactly once.

A graph formed from a subset of a graph's vertices and edges.