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

2
votes
2answers
35 views

Graph: Why the fact that there are at most $5-|B|$ independent path is a contradiction?

I don't understand why the fact that there is at most $5-|B|$ independent path is a contradiction (see picture below).
1
vote
3answers
25 views

Proving the number of leaves is larger by at least two than the number of vertices with a degree of at least 3

Prove that in every tree, the number of leaves is larger by at least two than the number of vertices with a degree of at least 3. Trying induction, I get something that is too short to be right, ...
0
votes
1answer
28 views

How to proove Hammer Split-graph Theorem?

Let $G=(V,E)$ be a Split Graph with $|V| \geq 4$. Then how to prove that: No induced sub-graph of G with 4 Vertices is a cycle with length 4 OR a pair of not incident edges? Well it must be from ...
3
votes
0answers
19 views

Reference for Lovász Theta being a lower bound on the fractional chromatic number

I have recently had a chance to think about the various known lower bounds on the graph chromatic number, and how they relate to each other. Having found no single place where these relations appear, ...
2
votes
0answers
22 views

Turan's theorem for balanced r-partite graphs

I'm curious about the following restricted version of Turan's theorem: Among all $r$-partite graphs that are balanced (exactly $n/r$ nodes per part), what is the maximum size of a graph with no ...
0
votes
1answer
22 views

Simple Undirected Graphs: Adjacency matrix and the $(0-1)$ incidence matrix

Are there any relation between the adjacency matrix and the $(0-1)$ incidence matrix of a simple undirected graph? They characterize uniquely the graph, so my intuition says there must be some ...
1
vote
1answer
64 views

Question about edge disjoint path

I'm studying about edge disjoint path. If there is 3 distinct vertices (u,v,w) in given Graph G = (V,E), Let there is u -> v has k (k>1) edge disjoint paths, and v -> w has k edge disjoint paths, ...
1
vote
1answer
29 views

Families of Sets, associate Bipartite Graph

For each of the following families of sets, construct the associated bipartite graph. If possible, find a system of distinct representatives. If there is no such system, explain why. A1 = {1, 2, 3}, ...
2
votes
1answer
61 views

Generalizing Hall's marriage theorem to arbitrary graphs

Given a finite graph G = (V, E) in which each vertex is a finite set, I call system of local representatives the choice for each vertex of one of its elements (the local representative), so that no ...
1
vote
1answer
33 views

Matchings in a Graph proof

Let M be a matching in an graph G. Prove that if P is an alternating path for M in G that begins and ends at unmatched vertices, then the matching M′ obtained from M by replacing the edges of M that ...
3
votes
0answers
21 views

Finding a cycle in a directed graph, however…

Say we have some directed graph, G. Every now and then, I can add either: a single arc from an existing vertex to another existing vertex (but no self-loops), add one new vertex with an arc to an ...
0
votes
1answer
21 views

Graph with chromatic index 1 billion more than max degree?

For a simple graph, Vizing's Theorem says $\chi '(G)\leq \Delta(G)+1$, where $\chi '(G)$ is the chromatic index (minimum size of an edge coloring) and $\Delta(G)$ is the maximum degree. I want a graph ...
3
votes
2answers
37 views

Regarding Max flow problem ( Ford-Fulkerson Algorithm)

I'm looking for the max flow in this graph but something is going wrong. First I take the path : 1-2-4-6. So the flow ie $F=1$ Then : 1-3-2-5-4-6 and the flow updates to $F=2+1=3$ If i take the ...
1
vote
1answer
22 views

Construct a plane embedding of a given $3$-regular graph

I`m struggling to understand a proof about general games which has single use path, and traversal location. My problem is that I can't understand what the authors says about "Construct a plane ...
0
votes
1answer
29 views

Degree distribution of the line graph of an Erdös-Rényi random graph

An Erdös-Rényi random graph is a graph, which consists of N nodes and where each link between them is present with probability p. It comes natural then that the pdf giving the probability of a node in ...
0
votes
0answers
15 views

Proving that the number of appearances of $i$ in $F(T)$ (Prufer sequence) is $d_i-1$

Let $T$ be a labeled tree on the set of vertices $\{1,...,n\}$, and its sequence of degrees is $d_1,...,d_n$. Prove that for all $1\le i \le n$ the number of appearances in $F(T)$ (Prufer sequence) ...
0
votes
1answer
23 views

Prove that a tournament is irreducible if and only if it is strongly connected

If a graph is irreducible, by definition there will be no source or sink and it will be strongly connected. Is my proof above good and how do I prove the converse?
1
vote
1answer
16 views

Prove that in the union of two trees there exist a vertex with degree of at most $3$

Let $T_1=(V, E_1), T_2=(V,E_2)$ be trees on the same set of vertices, and let $G=(V,E_1 \cup E_2)$ be the graph resulting from the union of the two trees. Prove that there exist a vertex with ...
2
votes
1answer
60 views

Graphical regular representation - specific choice of generators

From all I know the finite groups admitting a GRR are known completely. I currently try to use Godsil's results for some own ideas. That raises the following question: If $G$ is a given group that ...
1
vote
1answer
29 views

Graph theory and Combinatorics - how many walks?

The question is more combinatorial, but it is based on graph theory. How many walks with length $k$ does an $r$-regular graph with $n$ nodes contain? Well $r$-regular means that all nodes have $r$ ...
3
votes
0answers
41 views

Condition for a graph to have only one MST (Minimum Spanning Tree)?

Can somebody tell me if there is a condition for an edge-weighted graph to have exactly one MST? I know that it can have more minimum spanning trees, but can it have only one? Thanks in advance!
2
votes
2answers
52 views

A planar graph on $n \geq 3$ vertices has at most $3n-6$ edges: is the converse true?

I know by Euler's formula that if $G=(V,E)$ is planar on $n \geq 3$ vertices, then $|E|\leq 3n-6$. Is the converse true? If not, how to prove that le cube below is planar ?
1
vote
1answer
46 views

Graph: Coloring.

We consider the following graph $G$ (see picture below). I have to find a) A matching of maximum size, b) $\alpha(G)$ c) $\chi(G)$ d) $\chi'(G)$ which is a coloring of the edges. My answers a) I ...
0
votes
0answers
26 views

Graph: Prove that $\chi(G)+\chi(G^c)\leq n+1$ [duplicate]

Let $G$ a graph on $n$ vertices. Prove that $$\chi(G)+\chi(G^c)\leq n+1,$$ where $chi$ denote the minimum vertex coloring such that no two adjacent vertex has that same color. My proof (which is ...
3
votes
1answer
77 views

Probability of a particular randomly generated tree shape?

I start with a one-node tree. Then I repeatedly choose a node uniformly at random and add a child node to it, stopping when there are a certain number of nodes. Treating all nodes as equivalent and ...
22
votes
1answer
130 views

Smallest graph with automorphism group the quaternion $8$-group, $Q_8$

Frucht's Theorem states that for any finite group $G$ there is a finite (undirected) graph $\Gamma$ for which the automorphism group $\text{Aut}(\Gamma)$ of $\Gamma$ is isomorphic to $G$, and for many ...
1
vote
1answer
49 views

True or False. $K_{2n}$ ( complete graph with 2n vertices) has Euler circuit.

I believe this is true, correct? The reason is because it will start and stop at the same vertices. Am I correct?
2
votes
1answer
38 views

Prove that if G is a digraph who underlying graph is regular, then then following formula holds.

Prove that if $G$ is a digraph whose underlying graph is regular, then $$\sum_{i=1}^n\operatorname{outdeg}^2(v_i)=\sum_{i=1}^n\operatorname{indeg}^2(v_i)\;.$$ This is a assignment problem, so ...
-1
votes
1answer
57 views

Eulerian trail; graph theory question [closed]

Let $G$ be the digraph whose vertices are the pairs of integers $11, 12, 13, 21, 22, 23, 31, 32, 33$, and whose arcs join $ij$ to $kl$ if and only if $j=k$ . Find an Eulerian trail in $G$ and use it ...
1
vote
1answer
88 views

Pigeonhole principle, choosing 1-8 numbers out of 27

prove that for every 8 choosen numbers from 10 to 36 you can always make equalities. number can be used once. examples. let say that the choosen numbers are 10, 11, 12, 15, 18, 25, 32, 36 you can ...
0
votes
0answers
18 views

exist of k-critical graph

In the graph theory we have this theorem: my question is why exist subgraph $H^\prime$ ?,in every graph $G$ with $\chi(G)=k$ has k-critical subgraph $H$ ?
1
vote
1answer
36 views

when cartesian product of graph is perfect

What are the necessary and sufficient conditions for the following graph to be perfect? $ K_{1,n} \mathbin{\square} C_m $ $ C_n \mathbin{\square} C_m $ $ C_n \mathbin{\square} P_m $ ...
-1
votes
2answers
36 views

check if directed graph exists using ford fulkerson

Using Ford - Fulkerson algorithm, check if a directed graph with following degrees exists: $ d^+(x_1) = 2, d^-(x_1) = 2, d^+(x_2) = 0, d^-(x_2) = 1, $ $d^+(x_3) = 2, d^-(x_3) = 2, d^+(x_4) = 1, ...
0
votes
0answers
16 views

graph theory for matching more than two people

If I understand it correctly, then for studying matching pairs of people I could use the notion of matchings in graph theory. Is there a generalization of that for matching groups of more than two ...
4
votes
1answer
48 views

chromatic number for $k$-regular graph

Let $G$ be a connected graph that is $k$-regular and is neither a complete graph nor an odd cycle. Then the chromatic number of $G$ is $k$. Is it true?
0
votes
0answers
67 views

Hamiltonian bipartite graphs

Let $G$ be a bipartite graph with $n$ vertices and independent sets $U$ and $V$ such that $\vert U\vert=\vert V\vert=k=\frac{n}{2}>2$. I want to show that if $d(v)>\frac{k}{2}$ for every ...
0
votes
1answer
30 views

Matching in n by b bipartite graph

I found in a book the following corollary of Hall's theorem: Let $G=(A,B,E)$ be a bipartite graph. Suppose that $|A|=|B|=n$. If the minimal degree of $G$ is at least $n/2$ then $G$ has a matching. ...
2
votes
1answer
38 views

Graph embedding into a surface

For example, let's consider a $K_{5}$ (complete graph on 5 vertixes) and a torus, which is defined as $S^{1} \times S^{1}$. How to build a continous embedding $f:K_{5} \rightarrow \mathbb{T}^{2}$? We ...
0
votes
0answers
14 views

A matching M in a graph G is a maximum matching if and only if G has no M -augmented path.

Hi there is a theorem like this and there is a proof of that theorem. But i did not understand the proof even if i google it. Can anyone can help me with an understandable explanation? Theorem: A ...
0
votes
0answers
18 views

Matrix of node's ranking in a graph

In any graph of n nodes in any dimension, define matrix $M_r$ of ranking as $\forall r_{ij}\in M_r$, $r_{ij}$ is the ranking of j to i. That is, j is the $r_{ij}$th nearest node to i. Therefore, any ...
0
votes
1answer
33 views

Hamiltonian graphs of integers $n$

For which integers of $n$ is $K_{4,n}$ Hamiltonian? I know it is a complete bipartite graph, and there are $4$ vertices on one end and $n$ in the other. My guess is that $n$ would be the set: ...
1
vote
0answers
24 views

Graph: minor and topological minor

I still have problem with theses notion. Q1) How to prove that $K_7$ has $K_4$ as a topological minor ? Q2) Let $v_1,...,v_6$ a labeling of $K_6$ and let $G$ be the graph obtained from $K_6$ by ...
7
votes
1answer
108 views

$n$ points in the plane: show there are at least $\lceil \frac{n}{3} \rceil $ different distances between pairs of points

How can I prove that in each group of $n$ points in the plane, such that there are not $3$ points on the same line, there are at least $\left\lceil \frac{n}{3} \right\rceil $ different distances ...
1
vote
2answers
61 views

Prove disconnectedness of a graph is not generalized first-order logic definable

I have proved the connectedness of a graph is not generalized first-order logic definable. How about the disconnectedness? Is it also not first-order logic definable? (A property $\Phi$ of ...
2
votes
4answers
61 views

what is the maximum number of edges in a graph with self-loop?

If we have a graph G with n nodes, what is the maximum number of edges in this graph if we allow self-loop, is it n^2 and why, please look at the graph bellow: N=4, is maximum number of edges=16 or ...
0
votes
1answer
51 views

reduction from 3sat to 3 dimensional matching.

I've been reading about the standard reduction from 3sat to 3DM and my question was regarding the 'clean up gadgets'. So suppose i take an instance of 3-Sat with $n$ variables and $k$ clauses. Once we ...
0
votes
1answer
28 views

Given some k, is it possible to make a connected undirected graph G with vertex degree k, such that at least one edge in G is a bridge?

I know that an edge is a bridge if it does not lie on a cycle. This Math Exchange link tells me that any graph with vertex degree $(k)$ greater than $2$ has a cycle. So, I thought that no graph ...
0
votes
1answer
20 views

eccentricity of a vertex in hypercube graph

I have a question in graph theory ,my question is: find the eccentricity of every vertex in hypercube graph?,I know that in $Q_(k)$ eccentricity of every vertex is $k$ but I can't prove it.I read in a ...
1
vote
2answers
33 views

Graph theory, colourability in 3-space.

Can somebody explain colourability in $3$-space or share really good material that I can read? I understand the rules of $4$-colourability in planar universe: sections sharing the same border cannot ...
2
votes
1answer
35 views

Placing $n$ points so that their distances lie in $[1,a]$

What is the maximum number of points we can place in the plane so that the distance between any two such points is in the interval $[1,a]$? I had initially conjectured that the maximum could be ...