A subgraph of a graph G is a graph whose vertex set is a subset of that of G, and whose adjacency relation is a subset of that of G restricted to this subset. 

A subgraph H is a spanning subgraph, or factor, of a graph G if it has the same vertex set as G. We say H spans G. 

A subgraph H of a graph G is said to be induced (or full) if, for any pair of vertices x and y of H, xy is an edge of H if and only if xy is an edge of G. In other words, H is an induced subgraph of G if it has exactly the edges that appear in G over the same vertex set. If the vertex set of H is the subset S of V(G), then H can be written as G[S] and is said to be induced by S.

EXAMPLE: 

Degree  of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice.The degree of a vertex  is denoted  The maximum degree of a graph G, denoted by Δ(G), and the minimum degree of a graph, denoted by δ(G), are the maximum and minimum degree of its vertices.

 A walk is a sequence , , , ...,  of graph vertices  and graph edges  such that for , the edge  has endpoints  and . The length of a walk is its number of edges.

A walk is a trail if any edge is traversed at most once.

A trail is a path if any vertex is visited at most once except possibly the initial and terminal vertices when they are the same. A closed path is a circuit.

A cut vertex  is a vertex whose removal disconnects the remaining subgraph. A cut set, or vertex cut or separating set, is a set of vertices whose removal disconnects the remaining subgraph.

If it is always possible to establish a path from any vertex to every other even after removing any k - 1 vertices, then the graph is said to be k-vertex-connected or k-connected. Note that a graph is k-connected if and only if it contains k internally disjoint paths between any two vertices.

The vertex connectivity or connectivity κ(G) of a graph G is the minimum number of vertices that need to be removed to disconnect G. 

A bridge, or cut edge or isthmus, is an edge whose removal disconnects a graph. (For example, all the edges in a tree are bridges.)

A disconnecting set is a set of edges whose removal increases the number of components. An edge cut is the set of all edges which have one vertex in some proper vertex subset S and the other vertex in V(G)\S. Edges of K₃ form a disconnecting set but not an edge cut. Any two edges of K₃ form a minimal disconnecting set as well as an edge cut. An edge cut is necessarily a disconnecting set; and a minimal disconnecting set of a nonempty graph is necessarily an edge cut.

A graph is k-edge-connected if any subgraph formed by removing any k - 1 edges is still connected. The edge connectivity κ'(G) of a graph G is the minimum number of edges needed to disconnect G. One well-known result is that κ(G) ≤ κ'(G) ≤ δ(G).

A graph which is connected in the sense of a topological space, i.e., there is a path from any point to any other point in the graph. A graph that is not connected is said to be disconnected. 

Under code, finds maximum Wiener index  among all trees on n vertices with a fixed  diameter

 A k-coloring of G is an assignment of k colors to the vertices of G

in such a way that adjacent vertices are assigned different colors. If G has a k-coloring, then
G is said to be k-colorable.

 The chromatic number of G, denoted by X(G), is the smallest number k for which is k-colorable.

Let G be a graph with no loops. A k-edge-coloring of G is an assignment of k colors to the edges of G in such a way that any two edges meeting at a common vertex are assigned different colors,. If G has a k-edge coloring, then G is said to be k-edge colorable. The chromatic index of G, denoted by X`(G), is the smallest k for which G is k-edge-colorable.

Many graphs in SAGE can be drawn directly by their commands.

For Example:

Basic structures

Small Graphs

A small graph is just a single graph and has no parameter influencing the number of edges or vertices.

Platonic solids (ordered ascending by number of vertices)

Families of graphs

A family of graph is an infinite set of graphs which can be indexed by fixed number of parameters, e.g. two integer parameters. (A method whose name starts with a small letter does not return a single graph object but a graph iterator or a list of graphs or ...)

Chessboard Graphs

An Eulerian cycle, also called an Eulerian circuit, Euler circuit, Eulerian tour, or Euler tour, is a trail which starts and ends at the same graph vertex. In other words, it is a graph cycle which uses each graph edge exactly once.

An Eulerian graph is a graph containing an Eulerian cycle.

A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once (Skiena 1990, p. 196). A graph possessing a Hamiltonian cycle is said to be a Hamiltonian graph.
/span>

 Adjacency Matrix          인접 행렬                                          http://mathworld.wolfram.com/AdjacencyMatrix.html

The Adjacency Matrix, sometimes also called the connection matrix, of a simple labeled graph is a matrix with rows and columns labeled by graph vertices, with a 1 or 0 in position  according to whether  and  are adjacent or not. For a simple graph with no self-loops, the adjacency matrix must have 0s on the diagonal. For an undirected graph, the adjacency matrix is symmetric.

Given a simple graph G with n vertices, its Laplacian matrix  is defined as:

That is, it is the difference of the degree matrix D and the adjacency matrix A of the graph. In the case of directed graphs, either the indegree or outdegree might be used, depending on the application.

From the definition it follows that:

where deg(v_i) is degree of the vertex i.

The (ordinary) spectrum of a ?nite graph Γ is by de?nition the spectrum of the
adjacency matrix A, that is, its set of eigenvalues together with their multiplicities.

The Laplace spectrum of a ?nite undirected graph without loops is the spectrum of
the Laplace matrix L.