# Tag Info

## Hot answers tagged graph-theory

5

The complete tripartite graph $K_{3,3,3}$ is a $6$-regular graph on $9$ vertices and has chromatic number $3$ so it contains no $K_4.$ By Turán's theorem, a simple graph with $9$ vertices and more than $27$ edges must contain $K_4$ as a subgraph, and $K_{3,3,3}$ (also known as the Turán graph $T(9,3)$) is the unique $K_4$-free simple graph with $9$ vertices ...

4

\begin{align} \left|\bigcup_{v \in D} N(v)\right| &\leq \sum_{v \in D} |N(v)| \\ &= \sum_{v \in D} \deg_G(v) \\ &\leq \sum_{v \in D} \Delta(G) \\ &=|D|\cdot\Delta(G) \end{align} I hope this helps $\ddot\smile$

3

There is an index of notations in the book on page 573. If you look up "$\Delta$" in it, you see that this is the symmetric difference of sets: $$X \mathbin\Delta Y = (X \setminus Y) \cup (Y \setminus X).$$ It does not appear to be an operation on graphs, just on sets.

3

You could say that a digraph has this property if and only if all connected components are strongly connected. I'm not sure if there is one word for it.

3

How about molecules? The atoms are the nodes and the bonds are the edges. Or the nervous system? Receptors and the brain are nodes, neurons are edges

3

If $\lambda$ denotes the edge connectivity, then what is $$\lambda(K_{m,n}) , \chi(K_{m,n})?$$

3

The theorem says that a connected simple graph has an Euler circuit if and only if each vertex has even degree, and indeed that graph, in which vertices $A$ and $D$ have degree $3$, has no Euler circuit: there is no walk that traverses each edge exactly once and returns to its starting vertex. A companion theorem says that a connected simple graph has an ...

3

I will show that, if $G$ is any graph, then the Cartesian product $G\times K_2$ has a perfect matching. (In particular, $C_n\times K_2$ has a perfect matching for any $n\ge3.$) Suppose $G$ is a graph of order $n.$ Let $\overline{K_n}$ be the complement of the complete graph $K_n,$ i.e., $\overline{K_n}$ is a graph with $n$ vertices and no edges. It is easy ...

2

Clearly, since the sum of degrees across the 9 vertices must be even, there must be a vertex with degree at least $6$, meaning that only 2 vertices are isolated from this vertex. Choose the vertex of highest degree (degree-$6$ or higher) and label it as $A$ and the vertices connected it, the "linked set", as $\{B,C,D,E,F,G\}$. Each of these will have an ...

2

If $\chi(G)=3$, the graph cannot contain any $K_4$ as a subgraph: The above graph is just a $K_9$ with only $9$ edges removed, in particular a $K_{3,3,3}$, with chromatic number $3$, as clear from the picture (no couple of vertices with the same colour is joined by an edge, but the graph has plenty of embedded triangles). On the other hand, it is not ...

2

No, not by far. Suppose $m=\binom n2$ -- the claim is then that $K_n$ contains a maximum number of simple cycles among all graphs with $m$ edges. But $K_n$ has strictly less than $n!$ simple cycles, whereas we can also arrange the same number of edges into $\lfloor m/3\rfloor$ triangles strung together in a circle: * * * * * / \ / \ / \ ...

2

Any connected graph with $n$ vertices must have at least $n-1$ edges to connect the vertices. Therefore, $M=4$ or $M=5$ because for $M \geq 6$ we need at least 5 edges. Now, let's say we have $N$ edges. For $n$ vertices, there needs to be at least $n-1$ edges and, as you said, there are most $\frac{n(n-1)}{2}$ edges, so we need to solve the following ...

2

The slickest proof I've seen for this fact uses an entropy argument. The idea is to let $X = (X_1,\ldots,X_n)$ be a uniformly random vertex in $M$ and upper and lower bound the entropy $H(X)$. Using the chain rule and the fact that conditioning never increases entropy, we have \begin{eqnarray} \log_2|M| = H(X) = \sum_{i=1}^n H(X_i\mid X_{< i}) \...

2

Yes your ideas are correct. For the sake of not leaving this question unanswered, I'll refine your proof a bit. Proofs in graph theory have a tendency to naturally be broken into cases like your proof above. A lot of the time though, this isn't necessary, and you can make a proof more concise by trying to combine cases. For example, in your proof, ...

2

The most common way to express this is that component $c_1$ is not simply connected (it has a hole). Of course, this doesn't help to give a term for $c_2$, but in analogy with political maps, we might call it an enclave.

2

Obviously the definition of two edges being adjacent would be different from the definition of two vertices being adjacent. The only example you've given is that two adjacent edges are also said to be incident. Incident and adjacent are almost synonymous and I don't think you've really pointed out enough examples of overlapping or seemingly random terms. ...

2

No, not even if you strengthen "surjective" to require that every edge in $H$ is the image of at least one edge in $G$. For example, take $G=C_{10}$ (clearly planar) and $H=K_5$ (well known not to be); then a surjective homomorphism $f:G\to H$ would be given by $$\begin{matrix}f(0) = 0 & f(1)=1 & f(2) = 2 & f(3)=3 & f(4)=4 \\ f(5) = 0 & ... 1 The answer seems to be$$\sum_{k=1}^N\binom Nk2^{(N-k)k}.$$First choose a number k\in\{1,\dots,N\}, the number of vertices. Next choose a k-element set K\subseteq\{1,\dots,N\}. For each i\in K choose a set S_i\subseteq\{1,\dots,N\} subject to the conditon that S_i\cap K=K\setminus\{i\}. In other words, S_i=(K\setminus\{i\})\cup T where T ... 1 If you have 23 nodes then there are \binom{23}{2} = 253 possible links, assuming that any node may be linked to any other. If you had 24 nodes there would be \binom{24}{2} = 276 possible links, so 23 nodes is the most you can have if every pair of nodes must have a unique integer identifier n in the range 0 \leq n \leq 255. Number the links as ... 1 You could proceed in two steps: First, find the different matches over a set of runs: In terms of graph theory, you are looking for 10 distinct matchings with maximum cardinality in which vertices represent teams, and edges represent games between teams. In other words you want to color all the edges of a complete graphe with 12 vertices, with 10 colors, ... 1 Assuming that G has no isolated vertices: A vertex (say v_1) of degree \Delta will provide cover for all connected \Delta edges, which are associated with a total of \Delta +1 nodes. That is to say, for each vertex in the cover, it can "represent" no more than \Delta+1 nodes in the graph. And every vertex must be "represented" in some way ... 1 One way to quantify the complexity of a data structure (like your graph) is to determine its compressibility or "information content" as defined by Algorithmic Information Theory. What you'll need to do is encode each graph into a binary string. A simple convention is give here, where adjacency matrix is transformed into a string of trinary-values elements. ... 1 Considering network and complex systems applications such as the study of dynamics was a sufficient answer for me after learning basic graph theory. Although some of the further applications of network theory are not quite as 'clear', network theory is really where graph theory has been driven, giving way to new interesting research. Protein networks, ... 1 Ecological networks model interspecies relationships in an ecosystem. Nodes are species, and edges describe interspecies interactions of various types. A specific example is a food web in which the interactions are feeding relationships. 1 If the number of vertices is even, say 2m, we may label any vertex with an element of \mathbb{Z}/(2m\mathbb{Z}) and draw and edge between two vertices iff the difference between their labels lies in \{1,3,5,\ldots,2m-1\}. In such a way we have a m-regular graph with exactly m^2 edges and no triangle, essentially because the sum of three odd ... 1 Here is an example to disaprove the inequality. For a complete bipartite graph K_{3,4}, \lambda (K_{3,4})=3 and \chi (K_{3,4})=2. 1 A graph G is d-inductive if either G has at most d vertices or G has a vertex u of degree at most d such that G \setminus\{ u\} is d-inductive. Equivalently, G is d-inductive if its vertices can be numbered so that at most d neighbors of any vertex v have higher numbers than v. 1 The number of potential triangles containing some specific vertex v is {n-1 \choose 2}. Let [n] be the set of vertices of the random graph and let L = \{ \{s, t\}: s, t \in [n] \setminus \{v\}, s \neq t\}. Clearly, |L| = {n-1 \choose 2}. Moreover, any triangle containing v corresponds to an element of L and vice versa. So$$ \# \text{ of ...

Only top voted, non community-wiki answers of a minimum length are eligible