Definition

• Graph is a core if every homomorphism is an isomorphism
  Graph isomorphism
  In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
  
  , that is it is a bijection of vertices of .
• A core of a graph is a graph such that

1. There exists a homomorphism from to ,
2. there exists a homomorphism from to , and
3. is minimal with this property.

Examples

• Any complete graph
  Complete graph
  In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
  
   is a core.
• A cycle
  Cycle (graph theory)
  In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
  
   of odd length is a core.
• A core of a cycle of even length is .

Properties

• Core of a graph is determined uniquely, up to isomorphism
  Graph isomorphism
  In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
  
  .
• If and then the graphs and have isomorphic cores.

See also

• the k-core
  Degeneracy (graph theory)
  In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate...
  
  of a graph, obtained by iteratively removing all vertices of degree at most k, is a different notion.