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.

learn more… | top users | synonyms

1
vote
2answers
91 views

Graph parameters that are equal for small graphs

Do you know of any pretty well known graph parameters which are equal for all small graphs (for $|G|$ small)? That is, there exist two parameters $a(G)$ and $b(G)$ such that $a(G) = b(G)$ for all ...
2
votes
1answer
101 views

Possible relation between spectra bounds of two matrices

A Laplacian matrix $L\in\mathbb{R}^{n\times n}$, is a symmetric matrix with entries, \begin{equation} l_{ij}=\begin{cases} 1=\sum_{i,~ i\neq j} w_{ij} &\mbox{if } i=j \\ -w_{ij} & ...
1
vote
2answers
110 views

Determining the equivalence of two statements

I have been given two statements and told that they are equivalent, but I'm having a hard time convincing myself of that. The two statements are: (1) "Every graph G has a minimum colouring in which ...
0
votes
1answer
198 views

Maximal subtrees of connected graph

Are all maximal subtrees of a simple connected graph isomorphic? any hints?
1
vote
2answers
503 views

Existence of $k$-regular trees with $n$ vertices

a $k$-regular tree is a tree for which all vertices have a degree of $k$ or $1$ (internal veritces have a degree of $k$ and the leaves have a degree of $1$). I've been asked to find for which values ...
1
vote
0answers
92 views

It is possible to partition the vertex set of a graph $V=V_1\cup V_2$ so that … [duplicate]

so that at most half of all edges run within each part. This is seen by, for example, http://math.stackexchange.com/a/210609/44285 I am also asked to show that in addition to the above, one may also ...
3
votes
2answers
669 views

In a graph, the vertices can be partitioned $V=V_1\cup V_2$ so that at most half of all edges run within each part?

I am thinking of destroying all cycles of odd length by removing edges, so that I get a bipartite graph, with a partition $V_1$ and $V_2$ so that no edge in the new graph run within the two parts. ...
2
votes
1answer
408 views

Edge disjoint Hamiltonian cycles

The prism over Petersen's graph is Hamiltonian. Can you find two edge disjoint Hamiltonian cycles in this graph?
3
votes
1answer
279 views

Prove that a graph is Hamiltonian

Prove that if a graph $G$ is $k$-connected and $\alpha(G) \le k$ then $G$ is Hamiltonian. Where $\alpha(G) $ is the size of the largest independent set in $G.$
1
vote
2answers
195 views

What is a graph where edges are also vertices ?

Is there a name for a kind of graph where edges are vertices in the same graph ? A example would be : e1(a,b) e2(c,d) e3(e1,e)
1
vote
1answer
85 views

eccentricity of all the vertices in the strong product of two given graphs

I am trying to prove a result, where I have to show that the strong product of $K_{2}$ and $P_n$, n>2, is not self-centered graph, that is, eccentricity is not equal for all the vertices. the idea ...
0
votes
2answers
2k views

What is the “node weight” of a vertex?

I am reading a paper on weighted undirected graphs, and it states that if $A$ is the adjacency matrix of the graph $G$, then $a_{i,i}$ is the node weight of vertex $v_i$. What does this mean? Is ...
0
votes
1answer
170 views

3 coloring of vertices in a graph

How can we prove that there exists a coloring of vertices for graph $G$ such that at least 2/9 fraction of all triangles in $G$ whose vertices have different colors?
4
votes
1answer
185 views

Assigning alternate crossings to closed curves

This is a minor curiosity that I've been wondering about. Suppose that we draw a closed curve in the plane and that this curve intersects itself several times, but never twice in one spot. We can knot ...
5
votes
1answer
672 views

Every automorphism of a tree with an odd number of vertices has a fixed point

If $T$ is a tree, and $T$ has an odd number of vertices, then $\forall f$, where $f$ is automorphism $\Rightarrow \exists$ fixed point (vertex). What it means: Formally, an automorphism of a tree $T$ ...
1
vote
1answer
134 views

Why graph $G = (V, E)$ is elementary cycle?

If graph $G = (V, E)$ is bi-connected, and $\forall $ pair $(u, v)$ $u, v \in V$, $(u, v) \notin E$ graph $G - u - v$ is disconnected $\Rightarrow$ graph $G$ is the elementary cycle.
1
vote
1answer
451 views

How to prove the next properties for Critical graph?

This is a new question about Critical graph, because the previous question about it is became too big. Let me remind. In this context the Critical graph is: graph $G = (V, E)$ is Critical, if $G$ ...
3
votes
1answer
360 views

interpreting the power of adjacency matrix

Given a directed graph $G$, and let $A$ be $G$'s adjacency matrix, whose $(i,j)$-entry is 1 when there is an edge from $i$ to $j$. Is there any interpretative meaning of the $(i,j)$-entry of the ...
5
votes
1answer
207 views

Let graph $G = (V, E)$ $\Rightarrow$ $\alpha(G) \ge \frac{{|V|}^{2}}{2 \times (|E| + |V|)}$

Let graph $G = (V, E)$ $\Rightarrow$ $\alpha(G) \ge \frac{{|V|}^{2}}{2 \times (|E| + |V|)}$, where $\alpha(G)$ is the vertex independence number of $G$. Give some clue please! Thanks anyway!
0
votes
2answers
570 views

Proof for Full Binary Tree Using Handshaking Lemma?

I asked a question a few days ago and figured out the proof for this theorem using induction. ...
4
votes
1answer
109 views

Building a graph from pairwise distances

I am not familiar with graphs. However, I am curious about a question on graphs. Given a finite set equipped with a metric, is there any studying on the following problem? Problem: given the metric ...
0
votes
3answers
327 views

Algorithm to find all vertices exactly $k$ steps away in an undirected graph

This question may be better served at cs.SE, but I am not very familiar with CS lingo, so I'm hoping the maths community would be able to answer it as well... I have an undirected graph, and I am ...
2
votes
1answer
149 views

Graph Laplacian, requirements

What are the necessary and sufficient conditions for a PSD matrix $S$, to be a graph Laplacian? I know $S1=0$ is required. But clearly a real zero sum PSD matrix is not necessarily a graph Laplacian. ...
2
votes
1answer
699 views

What is the probability of having a cycle of length three in an Erdős-Rényi graph?

Given an Erdős-Rényi graph $G(n,p)$ (that is, a random graph where each edge exists with probability $p$), what is the probability of having a "triangle"? Given $3$ nodes in the graph, the ...
3
votes
0answers
97 views

Cut-distance between two Erdos-Renyi random graphs

Consider two Erdos-Renyi random graphs $G_1, G_2$ on $n$ nodes, with the edges in each graph generated independently at random with probability $1/2$. My question is about the cut-distance between ...
0
votes
1answer
688 views

Proving terminal vertices and total vertices of a full binary tree?

I am trying to make a proof by induction of the following theorem. ...
1
vote
1answer
98 views

Proving a graph contains a single node on a given level

Given that a graph contains a path between two nodes (A,Z) that has a distance which is strictly greater than n/2, is there a way of showing that the graph must contain a level in which there is only ...
2
votes
1answer
80 views

Let $G = (V, E)$ is a connected graph $\Rightarrow$ $\alpha(G) \le \frac{|E|}{\delta}$

Let $G = (V, E)$ is a connected graph $\Rightarrow$ $\alpha(G) \le \frac{|E|}{\delta(G)}$, where $\alpha(G)$ is the vertex independence number of $G$ and $\delta(G)$ − minimum degree of all vertices. ...
2
votes
1answer
114 views

$G$ is bipartite $\Leftrightarrow$ $\forall H$, $H$ is sub-graph of $G$ $\Rightarrow$ $\alpha(H) \ge \frac{|H|}{2}$

$G$ is bipartite $\Leftrightarrow$ $\forall H$, $H$ is sub-graph of $G$ $\Rightarrow$ $\alpha(H) \ge \frac{|H|}{2}$, where $\alpha(H)$ is the vertex independence number of $H$ Give some clue please! ...
0
votes
2answers
120 views

Permutating dance partners with least distance moved [duplicate]

Possible Duplicate: Gay Speed Dating Problem There are n (even) people at a dance and they dance in pairs. They do not care about gender (it is a very liberal disco). The goal is for each ...
0
votes
2answers
342 views

Finding the maximal complete subgraph which contains no monochromatic triangles of a complete graph

Given a 2-coloring of $\ E(K_n)$ such that a red edge belongs to no more than one unique Red triangle, show that $\exists \ K_k \subset K_n$ which contains no Red triangle, with $\ ...
6
votes
4answers
2k views

“faces” of a non-planar graph

Good afternoon, I have a question concerning concepts in graph theory. Graph theory is a field quite strange to my knowledge, so my question is maybe stupid. For a planar graph, we can define its ...
0
votes
1answer
49 views

Constructing a particular vertex coloring

My apologies for asking so many questions recently. Let $0\le c<d<e$ be fixed natural numbers and consider any graph on $2e$ vertices, with the vertices labelled as $0,1,\cdots 2e-1$. I want to ...
4
votes
1answer
377 views

The Hungarian Algorithm

In reading the proof of the Hungarian algorithm for the assignment problem in a weighted bigraph, I could not understand why the algorithm terminates. In the algorithm we choose a cover (namely labels ...
1
vote
1answer
115 views

If $\delta(G)\geq k$, does it implies $G$ contains a $k$-regular subgraph?

Let $G$ be a graph, and minimum degree $\delta(G)\geq k$, does $G$ contain a $k$-regular subgraph?
1
vote
1answer
242 views

Graph Isomorphisms, Delaunay Triangulation on a sphere, and Kulikowski's Theorem

Suppose I have a collection of $n$ non-collinear points on a sphere, $\left\lbrace P_i\right\rbrace_{i=1}^n $. And I construct a mapping from this collection of points to the Delaunay Triangulation ...
0
votes
2answers
405 views

How to approach proving things about large chromatic numbers?

What are some ways to prove limits to chromatic numbers, or what are some facts that I could when dealing with large chromatic numbers, such as in the question: Let G be a graph whose odd cycles ...
0
votes
1answer
218 views

Graph Theory - Clarification of type of graph

Just wondering if somebody can confirm the following: If I have some number of verticies, if there is only one edge connecting two of the vertices, can this be a bipartite graph, or do all verticies ...
4
votes
2answers
165 views

Which graph products are categorical products?

There is a whole bunch of definitions of graph products, but only one of them - the tensor product - is the categorical product in the (standard) category of graphs with graph homomorphisms. I'd ...
1
vote
4answers
5k views

Given the number of vertices in a graph, does the formula for max number of edges it can have make intutive sense?

I hope I'm able to put the question clearly. Suppose a pen costs x dollars, and I buy 3 pens. So the formula for total cost is : 3x This makes sense, since total cost is cost of one pen times number ...
1
vote
2answers
85 views

Acyclic graph (graph theory)

Let $v_1$, $v_2$, and $v_3$ be distinct vertices of a graph $G$ such that $G\setminus\{v_1\}$, $G\setminus\{v_2\}$ and $G\setminus\{v_3\}$ are all acyclic. Then prove that $G$ contains a maximum of ...
1
vote
1answer
53 views

Prove the following (graph theory)

Prove that a graph G contains no cycles IF AND ONLY IF the intersection of any two intersecting paths is also a path in G.
1
vote
1answer
150 views

Right adjoint to forgetful functor from “dynamical system” digraph

Question about "dynamical systems," as Lawvere/Schnauel calls them in their baby book (ie digraph w exactly 1 arrow out of each point). What would a "chaotic" dynamical system be? In the book's ...
3
votes
1answer
356 views

is there a way to find or upper bound the largest eigenvalue of the following matrix?

I have a matrix $A \in \{0,1\}^{n \times n}$ -- i.e. a matrix with 1s and 0s only. Is there a way to find or upper bound its largest eigenvalue? I have a feeling it is related to connectivity of ...
0
votes
1answer
216 views

A binary tree in 3-ary tree

We have an infinite $3$-ary tree, with root $R$. In coloring $C(p)$ each edge is black with probability $p$ and white with probability $1 - p$, and edges are independent. Show that there is a ...
2
votes
1answer
300 views

How to prove the non-obvious properties for Critical graph?

In this context the Critical graph is: graph $G = (V, E)$ is Critical, if $G$ is biconnected and $ \forall e \in E \Rightarrow G-e $ contains a point of articulation. $G-e$ is equal to if we remove ...
1
vote
0answers
104 views

maximum number of graph min-cuts, when edge-connectivity $c$ is odd

Based on the cactus representation of minimum cuts, it would seem that for a graph with $n$ vertices and edge-connectivity $c$, where $c$ is odd, that the maximum number of min-cuts is something like ...
16
votes
2answers
551 views

If $G$ is biconnected and $\delta(G) \geq 3 \Rightarrow \exists v: G-v$ is also biconnected.

If $G$ is biconnected and $\delta(G) \geq 3 \Rightarrow \exists v: G-v$ is also biconnected. Where $\delta (G) - $ minimum degree of all vertices, $G-v$ is equal to if we remove this vertex from $G$ ...
1
vote
3answers
2k views

How many of the 30 vertices in G have degree 3 and how many have degree 4?

A graph G has 50 edges and 30 vertices. Each vertex in G has either degree 3 or degree 4. How many of the 30 vertices in G have degree 3 and how many have degree 4?
3
votes
2answers
230 views

Why for number of leaves in a tree (all types of trees) is it true

I have to prove the following claim, given the tree $T=(V,E)$, $|V|\geq3$: $$|V_1| \leq \frac { |V| \times (\Delta (V) - 2) + 2 }{ \Delta (V) - 1 } $$ where $|V_1| - $ number of leaves in a tree, and ...