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

0
votes
2answers
17 views

Connecitivity graph. Easy task.

Let $G=(V,E) $ is a connectivity graph and $e\in E$ . Prove that $G'=(V, E - \{e\} ) $ is connectivity $\iff$ e is an edge $\in$ any cycle in $G$. Please help me with that.
0
votes
1answer
12 views

Why $f^{+}(v)-f^-(v) =val(f)$ if $v$ is the source?

I'm reading Bondy/Murthy's Graph Theory: He defines $x$ as the source and $y$ as the sink, reading a bit later in the chapter, he presents this definitions: $$ f^{+}(v)-f^-(v) = \left\{ ...
0
votes
2answers
14 views

Counting non-isomorphic graph.

How many exists non-isomorphic 4-regular graphs $G = (V,E)$ where $|V|=7$ vertices? I'm asking for hint to solve it with group theory( if it is possible) and without them
0
votes
0answers
13 views

Number of spanning trees for this graph

Find $\tau(G)$ for the graph $G$ below. This is what I tried so far: Let $e$ denote the horizontal edge between the two vertices as shown below. I wanted to use $\tau(G) = \tau(G-e) + \tau(G \circ ...
1
vote
1answer
18 views

Number of length-n paths in a graph with a fixed start vertex

So I was looking at a few past-years' papers from the ZIO (an IOI qualifier held here in India), and I found this question: I think this is the same as finding the number of paths of (let's take (a)) ...
0
votes
0answers
13 views

Every planar graph contains a vertex of degree $5$ or less to prove that every planar graph is $6$-choosable.

Use the fact that every planar graph contains a vertex of degree $5$ or less to prove that every planar graph is $6$-choosable. I understand the proof that every planar graph has a vertex of degree ...
3
votes
2answers
19 views

Proving a graph with $11$ vertices and $53$ edges is Hamiltonian

I have a graph with $11$ vertices and $53$ edges and I'm trying to prove it is Hamiltonian. I know that a graph is Hamiltonian if $n \geq 3$ and $d(v) \geq \frac{n}{2}$. I'm just having trouble ...
-2
votes
0answers
25 views

No perfect matching of k-regular graphs [duplicate]

I have to find, For each $k≥2 $, find a $k -regular$ graph that has no perfect matching. I found it true for $ k=3,4$ but don’t know how to write a generalised proof of it for all $k≥2 $. Kindly ...
0
votes
1answer
14 views

Alternatively eliminating vertexes from graph

Anna and John play on a graph G, alternatively selecting distinct vertexes from it such that for each i > 0, v[i] is adjacent to v[i−1]. Loses the one who can't select anymore a vertex. Prove that if ...
-2
votes
1answer
24 views

Perfect matching of a tree

I wanted to prove that a tree $T$ has a perfect matching if and only if $T-v$ $(v \in V)$ has exactly one odd component for all $v$ which are vertices of the graph. (An odd component is a component ...
-1
votes
0answers
12 views

k- regular graph matching [duplicate]

For each $k \geq 2$, find a $k$-regular graph that has no perfect matching. I found it true for $k=3, 4$ but don’t know how to write a generalised proof of it for all $k \geq 2$.
0
votes
1answer
28 views

Graph theory intro

For every graph G, prove that (vertex cover of G) is less than or equal to (twice it's matching). I tried a couple of examples and it works but I can't follow a trend to build my proof. Does anybody ...
1
vote
1answer
9 views

Partitioning a planar graph into spanning trees?

Suppose I have a simple, planar graph, which I want to partition into three edge sets such that each set forms a spanning tree. I've made an attempt at a solution, but it requires a few assumptions ...
-3
votes
0answers
11 views

Problem in Kernerl of Digraphs [on hold]

Prove that every digraph that is not kernel perfect contains a critical kernel perfect digraph. Where: A kernel K of a digraph D is a subset of D that satisfies: (1) Every pair of vertex in this ...
1
vote
1answer
9 views

Describe the automorphism group of the digraphs

Describe the automorphism group of the digraphs Here is what I got so far For $D_1$, because of the direction of $vw$, we can't do anything to the graph so $Aut(D_1)= I$ For $D_2$, we can flip the ...
4
votes
1answer
15 views

Proving an equality in degree function in an undirected graph

Given an undirected graph $G=(V,E)$, and a permutation $\pi$ of the vertices, denote by $\Delta_\pi$ the $\max_{1\leq i\leq n-1} \{\deg_{\{v_{i+1},...,v_n\}}(v_i)\}$. That is, we look only on the ...
3
votes
1answer
24 views

NP completeness path problem.

We have the following decision problem. Let $G=(V,E)$ be a directed graph with edge weights $w:E \to \mathbb{R}_{+}$ and $B \in \mathbb{R}$. Is there a set $K$ consisting of directed vertex-disjoint ...
2
votes
1answer
16 views

Determine the number of distinct labeling of $K_{r,r}$

Determine the number of distinct labeling of $K_{r,r}$ In $G=K_{r,r}$, every vertices has degree $r$ so $|Aut(G)|=r$. I also know that the number of distinct labeling of $G$ of order $n$ is $\frac ...
2
votes
2answers
37 views

Why this graph has automorphism group is isomorphic to the cyclic group of order 4?

My professor say that this graph is a non-separable graph whose automorphism group is isomorphic to the cyclic group of order 4 without telling me why I can see this graph has no cut vertex, so ...
1
vote
1answer
28 views

Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
1
vote
0answers
18 views

are graphs/networks additive

I was wondering if networks/graphs are the sum of their parts. Let's say you have a 15-node network. The spectral density of that network has X kurtosis and Y skewness. You also have a 20-node ...
1
vote
1answer
33 views

Graph Theory into

Let M and N be matchings in a graph G with (cardinality of M) > (cardinality of N). Prove that there exists matchings M' and N' such that (Cardinality of M') = ((cardinality of M)-1), and (Cardinality ...
1
vote
1answer
16 views

Minor Proof on a maximal planar graph

Let $G$ be a maximal planar graph of order at least $6$. Let $x$, $y$ be two non-adjacent vertices in $G$. Then $G + xy$ contains both $K_5$ and $K_{3, 3}$ as a topological minor. I am lost on this ...
3
votes
1answer
28 views

Graph theory proofs

I am trying to prove that half of the vertex cover of graph is less than it's matching number. The problem is I don't know how to start and what the solution should be like, please help!
1
vote
1answer
99 views

A sequence of $n^2$ real numbers which contains no monotonic subsequence of more than $n$ terms

I'm following a Combinatorics course at the moment, and have recent proved the Erdős–Szekeres Theorem (or, at least, some variation of): A sequence of length $n^2 + 1$ either contains an ...
1
vote
0answers
28 views

Random Spanning Tree Edge Probability

I am working on a problem with a Loop Erased Random Walk used to create random spanning trees from a graph. The problem has many parts, but there are two hints to help with the more complicated ...
0
votes
1answer
16 views

Find a graph $H$ such that $H$ is a minor of $G$ but not a topological minor of $G$. [on hold]

Let $G$ and $H$ be simple graphs. Find a graph $H$ such that $H$ is a minor of $G$ but not a topological minor of $G$. Any ideas of how to do this problem? Any help is greatly appreciated, thanks.
0
votes
1answer
11 views

Measure for presence of several poorly interconnected components in undirected graph

Is there a measure to classify networks regarding whether or not they are composed of several (internally closely connected) groups which are poorly connected (i.e. few links between groups). That ...
0
votes
1answer
5 views

Scale free networks (power law)

I'm working with a dataset, of which I'm analysing the degree distribution. I'm finding that it obeys the famous power law/scale free degree distribution $\propto k^{-\gamma}$, but the value of ...
0
votes
1answer
24 views

Is my idea of incoming/outgoing arcs correct?

I'm reading Jungnickel's Graphs, Networks and Algorithms. I've met the following lemma: I know that $e^{-}$ are the incoming vertices and $e^{+}$ are the outgoing vertices. Then I've tried to ...
1
vote
2answers
33 views

Whether the graphs G and G' given below are isomorphic

Whether the graphs G and G' given below are isomorphic?
4
votes
2answers
30 views

Graph contains triangle

Prove that if a simple graph of order n has more than n^2/4 edges then it contains a triangle. I know Martels theorem states the opposite condition for a triangle free graph but I'm not sure how to ...
0
votes
2answers
15 views

Node with loop graph completion

Is a graph consisting of a single node complete in addition to being simple? What about a node with a self loop:it's not simple but is it complete ?
1
vote
1answer
25 views

graph theory - clique graph

I am trying to understand the concept of clique graph. So I found this page. But I do not understand the example and what "graph intersection" is. Can somebody explain to me why $K_4$ is a clique ...
6
votes
0answers
61 views

Number of sets of vertices whose union of neighbours contains exactly $k$ vertices

Suppose a bipartite graph $g$ consisting of $2n(n-1),n\in\Bbb N,n>1$ vertices, is divided equally into two colors: red and blue, and is constructed as follows: For example, $g$ for $n=3$: If ...
0
votes
0answers
21 views

Lovasz number and bipartite complement

Let $G=(V,E)$ be a graph on $n$ vertices. An ordered set of n unit vectors $U=(ui|i∈V)⊂R^N$ is called an orthonormal representation of G in $R^N$, if $u_i$ and $u_j$ are orthogonal whenever vertices i ...
0
votes
0answers
11 views

Positive definite functions defined on the embedding of a planar graph in the plane

By way of motivation: Let $f:[0,1]\rightarrow\mathbb{R}^2$ and $g:\mathbb{S}_1\rightarrow\mathbb{R}^2$ be continuous injections, where $\mathbb{S}_1$ is the circle ($\mathbb{R}/\mathbb{Z}$). Then, ...
2
votes
0answers
17 views

Double circle representation using ideal rubber bands

Let $V$ be a 3-connected planar graph, $V^*$ be its dual graph. Let $(C_i : i \in V)$ and $(D_p : p \in V^*)$ be a collection of circles so that if any edge $\{i,j\}$ borders any faces $a$ and $b$, ...
1
vote
0answers
31 views

The circumference of a hypercube graph

How can I find the circumference of a hypercube graph? is easy to see that a n-dimensional hypercube have a $2n$-cycle, but I cant prove that it's the largest, can anybody help me?
0
votes
1answer
13 views

Every nonhamiltonian 2-connected graph has a theta subgraph

If a graph $G$ has a spanning cycle $Z$, then $G$ is called a Hamiltonian graph and $Z$ has a Hamiltonian cycle. A theta graph is a block with two nonadjacent vertices of degree 3 and all other points ...
6
votes
3answers
82 views

Secret Santa Perfect Loop problem

(n) people put their name in a hat. Each person picks a name out of the hat to buy a gift for. If a person picks out themselves they put the name back into the hat. If the last person can only ...
1
vote
1answer
38 views

Graph and one Sequence challenge

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
1
vote
1answer
12 views

P - bounded polyhedron, L - linear map. Show that L(P) is a bounded polyhedron

Let $P = \{x\in \mathbb{R}^n \ | \ Ax\leq b\}$ be a bounded polyhedron. Let $L:\mathbb{R}^n \rightarrow \mathbb{R}^k$ be a linear map. Show that $L(P):=\{L(x)\ | \ x\in P\}$ is a bounded polyhedron. ...
0
votes
0answers
14 views

Is this a Red-Black Tree?

I tried to build RBT (Red-Black Tree) via this way: I build a balanced binary search tree (much as I can) and then colored it... Now the Q is: if this is a legal RBT? At my opinion is yes, because ...
3
votes
1answer
52 views

Graph with only the identity as endomorphism

Is there a graph $G$ with more than one vertex such that the identity $\textrm{id}: G\to G$ is the only graph homomorphism from $G$ to itself? Is there even an infinite example?
1
vote
1answer
21 views

Show that $\delta(G) \geq 4$ if $\chi(G)=5$ and $\chi(G-v) =4$ for each vertex $v \in G$

Let G be a graph satisfying the following conditions: (1) $\chi(G)=5$ and (2) $\chi(G-v) =4$ for each vertex $v \in G$ Show that $\delta(G) \geq 4$. Answer given: Suppose $\delta(G) \leq 3.$ Let ...
0
votes
0answers
14 views

Graph Minor/Subdivision Proof

Prove that if $G$ contains a $K_5$ or $K_{3, 3}$ minor, then $G$ contains a $K_5$ or $K_{3, 3}$ subdivision. Any proofs or hints are greatly appreciated.
0
votes
1answer
16 views

Does the maximum cut implies the minimum flow?

Is it possible to reverse the result of the min-cut max-flow theorem and obtain the result that if you have the maximum cut, then you have the minimum flow? I've been thinking about it, but I have no ...
0
votes
0answers
10 views

Upper bound for graphs with no k-cliques

We know that for random graphs $G(n,p)$ we have: $P[X=0]\leq e^{-\Theta(E[X])}$ where $X$ denotes the number of k-cliques in the random graph. Can this fact be used to say anything about the number of ...
0
votes
0answers
6 views

Algorithm for creating a directed scale free network with a fixed amount of nodes

I'm trying to figure out an algorithm that produces a scale free, directed network, for which I can give the final amount of nodes as an input. Now, this is a little bit tricky for a few reasons, so ...