# Questions tagged [graph-theory]

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

23,235 questions
Filter by
Sorted by
Tagged with
1 vote
21 views

### Edges of a $K_4$ cannot be too short

This problem arised while I was working through Erdös-Bollobas's solution for Ramsey-Turán Problem however i believe that details for that isn't necessary. Consider the following construction \begin{...
1 vote
21 views

### Meaning of $\mathbb{R}^E$ in graph theory

I'm reading through Lovasz's paper on discrete analytic functions but I'm confused about how the coboundary of a node $\delta v$ is defined. What does $\mathbb{R}^E$ mean on page 243 where $E$ is the ...
34 views

20 views

81 views

### How many automorphisms does this graph have? [closed]

How to calculate it? Here is the picture: I have been thinking. 0 cant move anywhere. 1 can swap only with 2. 3 only with 4. 5 only with 6. 7 8 and 9 can swap individually as needed. Now the problem ...
74 views

40 views

41 views

### graph theory trees and cuts

Could someone explain why these statements are true or false? Every tree has an vertex-cut of size 1 (False) Every tree has an edge cut of size 1 (False) I thought they were true?
39 views

### using $P$ in place of $P^T$ when doing graph isomorphism through matrices

Let $G,H$ be simple graphs, and $A_G,A_H$ their adjacency matrices. Let $P$ be a permutation matrix, representing the permutation $\pi$. I'm currently trying to understand why two graphs are ...
21 views

1 vote
48 views

### Show Tree Proof is Incorrect

It seems the part that says every vertex in H has degree at least two is not necessarily true. The paths could converge prior to seeing vertex v, thus resulting in at least one vertex having degree 1. ...
56 views

### Sum of squares of chromatic roots of a bipartite graph

Given a graph $G = (V, E)$, we can calculate its chromatic polynomial $P(G, k)$, and it has $n$ (complex) roots, also known as chromatic roots. It is a well-known fact that the sum of chromatic roots ...
299 views

### What is the type of this directed graph?

Let $G=(V,E)$ be a directed graph. Suppose that $G$ has the following properties: the vertex set $V$ is partitioned into $T$-parts $V_0,V_1, \dots, V_{T-1}$, and for any edge in $E$, if its initial ...
31 views

### Erdős–Rényi graph with degree $O(1)$ High dimensional probability [closed]

Consider a random graph $G=G(n,p)$ with expected degrees $d=O(1)$.Show that, with high probability has a vertex whose degree is at least of order $$\frac{\log n}{\log \log n}$$.
18 views

### Number of Iterations to maximize flow given recurrence relation

I have proven that there is always an augmenting path of capacity at least $\frac{F}{|E|}$. How do I use this to bound the number of rounds given that I use a relation to increase the flow by a ...
2k views

### Can a hexagonal grid embed rectangular coordinates?

I'm trying to figure out if a hexagonal grid can embed rectangular coordinates in whole numbers of "Y-steps". In the image below, one "Y-step" is the spacing between red hexagon ...
184 views

### Why does a 3-regular planar graph of diameter 3 have at most 12 vertices?

Today, I saw an interesting exercise on page 224 of the West textbook "Introduction to Graph Theory". 6.1.15. Construct a 3-regular planar graph of diameter 3 with 12 vertices. (Comment: T. ...